Please don't consider this reply as authoritative on the subject, somebody else will come along soon and provide that. Like you, I was faced with a similar problem recently...

Windows Server 2003 can employ a "previous versions" technology where for selected locations (network shares), n shadow copies are kept of modified/deleted files. See if this has been enabled on your server. If it has, you need to install the Previous Versions client application within XP etc. to access them across a network. You could try right-clicking the folder that held the deleted file and see if it's there on the context menu.