Personal address and contacts are stored locally, not on the Exchange server. Do a search on the local drive for any *.pst files. If an archive was set up (manual and/or auto)and a .pst file exists, you should be able to connect to it via Outlook. Hopefully the contacts will be present.
If a .pst file exists:
From Outlook (this example 2003) go to file -> Open -> Outlook data file... -> browse to the location of the .pst file and open it.
If a .pst file does not exists, I would suggest training your boss on how to backup his local outlook files using archiving.
From Outlook go to file -> Archive -> choose mailbox (which will include calendar, Contacts, inbox, etc...).
Set Archive location (either local or a Network Share) and save.
Also look into Auto Archive Settings to set-up a scheduled archive.