It sounds like the contacts were in BCM and not synced with outlook. Restore the old database to get the contacts back, then export them to a pst.
FWIW, i would try cleaning up the database instead of creating a new one - if you link email to contacts, removing older messages can free up space.