Not much I can say other than try a reboot. VoiceMail app could just be hosed in memory and a fresh reboot could help.
Try a reboot (described below).
Think of it this way, the iPhone is more of a computer than a phone. It suffers from being a new OS and nobody can deny there are not bugs and memory leaks. The longer left running, the more things start to fail or slow down (I have had the iPhone since day one of original phone and I am just speaking from my experience). Thus I equate it to like when Windows95 came out...not sure of your age or if you remember those days...but back then it was a running joke of how many days you can keep Windows 95 running before you had to reboot. I am sorry to say but the iPhone is the same way right now (but getting better with a few hiccups back during the 2.0 release). So for me, I reboot daily when I leave in the morning and take it off the charger. By doing so I rarely see any lag or problems.
A reset/reboot is:
Go to Home Screen
Press and Hold Home Button
Keep holding and press and hold Lock Button
Keep holding Both
You will see Slide to Turn Off (Don't let go to slide, just keep holding)
The phone will turn off (in time, but screen will look like it has some white lines)
Keep Holding
When you see the Apple Logo, you can let go.
Turning off via the Slide to Turn off while good and fine to turn off, is more like the Sleep Mode on a computer. Thus any locked up issues in memory remain when you turn back on. A reboot as described is like doing a real Turn off and Turn On on a computer.
You may also wish to read this tread about reboots and odd application behavior.
http://discussions.apple.com/message.jspa?messageID=5851978#5851978
