I once had a problem finding an app that I knew was installed. The solution turned out to be fairly obvious but I hadn't spotted it.
If you go to Settings->Applications->Manage applications
there are tabs and the default is Downloaded. Once I selected All next to it I could find the app I was looking for. This may not be the cause of your problem, but then again, perhaps it is so it's worth checking.