I have some thoughts ...
1- If the problem is Outlook attachments, the default Save As location can be changed in the registry .. MS support site instructions for Outlook 2003 are here.
2- If the problem is primarily around MS Office you can change the default file save location (instructions here), and you might be able to use Office Resource Kit group policy templates to control things like default save location.
3- Upgrade him to Windows 7 .. the "library" feature plus vastly improved search capability should at least reduce the pain caused by his inability to keep things straight.
4- In the alternative .. Windows Desktop Search or Google Desktop might also be helpful to get him a better search tool.
5- I like the idea of restricting his security so that he can't save in undesirable places. This will take work to figure out how to do properly, especially to do it in a standard manner, and he likely will not like it.
Finally .. perhaps the best solution is to let him struggle with the problem. When it hurts enough he will correct the unhelpful behavior. The problem here is putting up with the