I mean, it seems rather simple, no? Press the # key to skip the message and leave your voice mail. This works in many cases, but other times, when you press #, you are greeted with a message that says "Please enter your password" and then you're stuck. The only option is to call again, then listen to the entire greeting (which is sometimes obnoxiously long), followed by the moron-specific instructions (e.g. "please wait for the beep to leave a message. When you are finished, you can hang up or press the pound key for more options." Argh! It makes me want to throw the phone across the room!
Try calling yourself and see how long it takes for you to leave a message. If a caller can't leave a message in less than 15 seconds (even 10 seconds) then your system needs fixing. This can be as simple as saying "Press 1 to leave a message immediately. Hello you've reached Laurent Duperval, and let me tell you about my life..."
Of course, you can always try to get your phone carrier to fix their system to allow # instead of some other key.