The contacts are stored in a pair of SQLite databases on the phone, so the only limits are limits imposed by SQLite and the processing power of the device.
The short answer is: you're not likely to run into a problem unless you're trying to do something extremely large scale, like write a company directory app for the ~1.6M Indian Railway employees or capture all of the ~200M US registered voters. I've created a database with all US zip codes and another with multiple mappings to all English, German, French and Spanish words from the standard Linux spelling dictionaries and have not run into problems. The latter had a table with more than 3 million records and runs fine on an original iPhone.
You're more likely to run into machine performance limits before an absolute limit on the number of records. For example, consider this from the SQLite site:
When you start a transaction in SQLite (which happens automatically before any write operation that is not within an explicit BEGIN...COMMIT) the engine has to allocate a bitmap of dirty pages in the disk file to help it manage its rollback journal. SQLite needs 256 bytes of RAM for every 1MB of database. For smaller databases, the amount of memory required is not a problem, but when databases begin to grow into the multi-gigabyte range, the size of the bitmap can get quite large. If you need to store and modify more than a few dozen GB of data, you should consider using a different database engine.
So, (if my math is right) a 30G database would require 7.5M of space for the bitmaps during an INSERT. This may be hard on a first gen iPhone (only had 64M RAM and 16G Flash, besides), but maybe OK on later models with more memory. That said, before you get to this many records, updating the indexes or asking the AddressBook.app to display them may result in unacceptable performance.
If you want to explore the AddressBook schema, create a single contact in the simulator, then in a Terminal window:
% cd "~/Library/Applications Support/iPhone Simulator/4.0.2/Library/AddressBook"
% sqlite AddressBook.sqlitedb
sqlite> .schema
This is, however, an excellent example of why you must test your app on a real device before submitting it to the store. Such an app will run without issue in the simulator's 3.0GHz, multi-core, 4GB RAM environment, but not so well in on a 1/2 GHz 2nd gen iPod Touch.