I found this on another forum. Not too effective if you aren't jailbroken:
You're iPhone will have to be jailbroken so you can ssh into:
/private/var/mobile/library/addressbook
You then copy out AddressBook.sqlitedb
It would be best to create a backup of this just in case something goes wrong.
Then what you'll need to do is open the file with a SQLite Database manager, I for example downloaded Visual SQLite (for free) off of download.com.
Then after installing and opening the file (AddressBook.sqlitedb) you can go ahead and delete the contact you wish to remove by:
Under Table selecting: ABRecent
Selecting the Table Data tab
And then scrolling down, finding the person, and....delete
So then you save the file, ssh it back to the same folder in your iPhone, replacing the existing one.