A feature new to Windows Vista is the Games Explorer, a folder dedicated to the games installed on the computer; games are required to exclusively add themselves there as part of the Games for Windows technical requirements, and Microsoft provide details of hundreds of pre-Vista games which appear automatically as a result.
Unfortunately, you can't search this folder directly from the Start Menu. While this is an annoying problem, it's not insurmountable. In fact, it's pretty easy to manually rectify with a short bit of scripting.
Update Games Explorer is a short Command Script to enumerate the contents of your Games Explorer and copy the shortcuts into the Games folder in the Start Menu, thus rendering them indexed and searchable. The script can be run directly or as a scheduled task, whichever suits best.