I'm sure you checked, but have you got the right password for voicemail. It is on the screen when you first logon to the voxalot website. Maybe 9999 is not the right one?
You could also try accessing it through SIP Broker (
http://sipbroker.com/sipbroker/action/pstnNumbers) to see if it is your phone or your voxalot account that is causing the problem. At the voice prompt dial *031500#. Try it from a mobile or POTS phone to be sure!