The existing map history for ArcMap 9.3.x (and possibly other versions) is stored in the user's registry.

This is the dialog box that is shown be default when a user starts ArcMap.

To clear the history, open regedit and go to: HKEY_CURRENT_USER\Software\ESRI\ArcMap\Recent File List\
Delete File1,File2,File3,etc. and the next time you open ArcMap, your existing map history will be empty.

Another option is to  pre-populate the registry with entries for new GIS users.