There is a known problem with voicemails received from SkypeIn. The voicemails may be delivered with a considerable delay. To force immediate delivery, you need to use the "Sign out" function of Skype client, and then sign back in manually with your Skype Name and password.

We apologize for the inconvenience this causes and are working on a system update to fix this.

UPDATE Dec 11: work is ongoing to fix this and we're rolling out the fixes to our systems. We will post new info before the end of the year.

UPDATE Dec 15: this has now been fixed.