I hate when the stock Apps seem to disappear. This happened to me and my husband once. He has a lot of Apps and a weird arrangement of folders on his phone. He insisted he erased his Contacts App by mistake because it wasn't there. I looked through his many folders and found it nestled in a folder. It got moved. Probably a pocket move or sometimes when you hold your phone you can get the Apps to wiggling and then when you put it in your pocket or just by handling your phone, you can inadvertantly move Apps. That's what I think happened to him.
This happened to me also once with my 3GS. My Camera App went missing. I searched or it and couldn't find it so I just did a hard reset and it came back. My 3GS was wacky.
Your missing App could be hiding in a folder or just on a page you wouldn't expect it to be. Take a look and do a search with spotlight for the App to make sure it is still on the phone.