Most wireless companies also have a seperate "voicemail retrieval #" that can be obtained through their customer care, this will allow you to call and usually get right into your voice mail without having to hit the # or * key.
There is also a setting in most voicemail's that allows you to set it so that it does not ask for a password.