Try Xobni search plugin - it's fast and free for the basic version. It will certainly alleviate your search pains with Outlook 2003.

So it sounds like you're using Outlook 2003 on XP and don't have Windows Search (what powers Outlook instant search) installed.

Hound your incompetent IT department and say you need to search your email and you need Windows Search 4 installed on your machine instead of blaming a 6 year old product and a 8 year old operating system.

If you're stuck on Outlook 2003, Lookout is an add-on for '03 that adds blazing fast search. I find it works faster than Xobni.