It would require shuffling around the system calls, but in all fairness, Windows 7+ has an integrated feature very similar to Spotlight. In fact indexing has been around since at least Windows 2000.
The bigger issues would probably be the UI and other OS-level integration points. The sheer number of them overall, depending on the architecture could be pretty staggering. I'd love to have Alfred be cross-platform as well, but I can see that it might be difficult.
Launchy is cross-platform and looks superficially similar: http://www.launchy.net/
I used to use SlickRun on windows: http://bayden.com/slickrun/
On Linux Krunner is built into KDE. There's gnome Do but its more similar to Quicksilver. There's also Synapse for Gnome.
Check out AlternativeTo for more possibilities: http://alternativeto.net/software/alfred/?platform=windows
