Firstly, if the contacts you've lost from iPhone #2 are the same as the ones on iPhone #1, and you've been syncing them with the same Mac, then you should be able to simply turn on contact syncing for iPhone #2 and they should be restored via the iTunes sync process.
If they aren't the same, or if there were contacts on iPhone #2 that aren't stored on the Mac, then assuming you haven't synced iPhone #2 with iTunes since the contacts were removed, or if you have a backup of your computer from before the contacts were removed, you could try restoring iPhone #2 from the last backup iTunes made.
It's important to note that if the backup is old enough that it doesn't include things you do want (like text messages you've received, or photos you've taken since the backup was made), because restoring an iPhone from a backup replaces all the information on it with what the backup has, those things will be lost as well.
If you're unsure if the backup iTunes has of iPhone #2 was made before or after the contacts were lost, ensure iPhone #2 isn't connected, then open iTunes, click the iTunes menu, Preferences, then on the Devices tab, check the date/time of the backup listed next to iPhone #2.
If the backup is from before the contacts were lost and you want to restore iPhone #2 from it, first ensure that in that same window, the box next to "Prevent iPods, iPhones, and iPads from syncing automatically" is ticked, click OK, connect iPhone #2, once it shows up in iTunes, right click it in the iTunes source list (on the left), select Restore from Backup... and choose the backup you want to restore from.
hopkapi, thanks. It worked. I figured out what the problem is. I tried to set up iPhone #2 with a new exchange server in a new company. The contact list in iPhone #2 was sync-ed to the old company's exchange server. When I remove the email account with the old server, the contact list is removed as well. Is there any way to copy the contact list and store it locally on the iPhone #2 and then sync them to outlook on a new PC? Yes, I now would like to sync iPhone #2 with a PC. Then, totally separate from iPhone #1 and the Mac.