1- you might have clicked menu key > Move To > and put it in another folder... (Like Downloads or something).
2- The above was not the case for me. I had to delete and reinstall the Visual Voicemail
Thanks for the suggestion that an icon can inadvertently be moved to a different folder.
After having the screen freeze on me for about five minutes, it woke up with a missing Messages icon. Having done nothing to move it myself, I browsed the folders only to find it in Downloads... Now, how the heck does that happen?