You could always update the UI on the assumption that it will succeed, and then check the return value. If you get failure, notify the user somehow. Making the UI seem a slight bit more responsive might not be really worth it, of course.
I think the standard solution here would be not to lie to the user. A quick sending graphic, which is replaced with a received graphic would accurately portray the events that are happening. These could easily be iconic, maybe just a differently colored arrow while sending, which fades out when it's sent.
Definitely true, especially for something like up-voting. I mean, it might fail on 0.1% of clicks, but 0.1% accuracy on a vote is pretty good.
I guess if one was really concerned, you could update the UI immediately like News.YC does, and then change it back or show an error if it does happen to come back failed.