The default search only looks for Start Menu shortcuts and other indexed files, not all applications. Thus, it is quite likely that Media Center is still intact, just missing a shortcut. Try pressing WINKEY + R and entering %SystemRoot%\ehome\ehshell.exe into the box that appears. If Media Center launches all you'll need to do is browse to C:\Windows\ehome, right-click ehshell.exe, and select "Pin to Start Menu."
Hope this helps,
I got HP a1747c PC with window Vista Home Premium. For some reasons, the Window Media Center disappeared on my PC. No icon, no program, no trace. I do search on start button, but no WMC. I discover the WMC mising after I install Roxio 2009, but I remember I do not disable or replace the DVD player from WMC to Roxio Movie player. Please help.