A few weeks ago, I tried a Vista styled start menu replacement for XP called Vista Start Menu. It worked nicely and even included the Vista style program search. This one seems to give you an even better simulation and the search feature is even faster than what Vista can give you. The only issue I had with this utility is a slow start-up time.
The ViOrb tool is a separate utility that replaces the green Start button with the fancy Vista styled Windows logo. I tried it out but I was much less impressed with it.
Here's where you can find both of these programs.