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.