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.