For Outlook 2000-2002, each Contact folder can store up to 64,000 entries.
You can have multiple Contacts folders, so in any single PST, you can have
up to 4,096,000,000 contacts.  Of course, you can have multiple PSTs as
well.

For Outlook 2003, I don't know what the limit is, but you can have more than
64,000 contacts in each COntact folder and more than 64,000 contacts folders
in a single PST.  Naturally, you can still have more than one PST, so
there's no real practical limit.

I have no idea if there's a limit in the Windows Address Book (what Outlook
Express uses).