You're not alone. I'm on a mac, but pick up my calls on a Linxys iPhone (heh) system, and others on the PC side are seeing the same thing:
I think it's their servers, not our computers. (Hooray, Windows for taking over Skype and breaking it!)
We've been able to "get around it" albeit at some trouble by making a call, then hanging up and the voice messages come in. Try that mbmark!
(I'm moving off this system shortly because I can't have my work calls coming in hours later or keep having to guess if someone called if I walked away from my desk.)
I have the same problem too and am on Windows... it is driving me nutty. I get the email notification and there is no voice message to be found.
Ive tried the tip of making a call and yes - this has worked!!!! I'll also lagit as a problem though as its not reasonable that we should hav to do this to pick up mail!