I am talking about the hotkey to quickly begin typing into the Windows Search deskband on Windows XP (instead of clicking inside the box with the mouse) and not about Win+F. As mentioned in this cool tip here, you can define your own hotkey for this and remove the Win key requirement if you do some registry tinkering. Be careful while modifying the registry, if you are inexperienced, back up the registry key or the entire registry. I set it to Ctrl+Space (something that be hit without looking at the keyboard). While it doesn't give you the convenience of Start Search present in Windows Vista and later operating systems, it does give you a very accessible keyboard shortcut that makes your deskband as "killer" as Start search.
Note: Make sure Ctrl+Space doesn't conflict with the apps you use. For example, if you are using the language bar, Ctrl+Space is used to switch the IME. In Windows Explorer, you may be using it for multiple file selection. It is also used in Emacs, Word or Eclipse. If it conflicts, you should change the keyboard shortcut in the app if configurable. For the language bar, the hotkey can be changed in "Text Services and Input Languages" accessible from the Regional and Language options control panel.