A good cataloging program is Microsoft Expression Media, which is really just the old iView Media. I think it's only good for a few hundred thousand shots, so you might be out of luck if you need to catalog millions of photos.
What I do is use Filemaker Pro to catalog the jobs, and then store them on DVD disks in a filing cabinet. I can lay my hands on all of my jobs easily, and all I keep on hard drives is the web sized versions for reference.
David buzzard's technical blog