It's actually a bit buggy, I think the data is stored in a bit of a non-standard way.
From my phone, I was unable to remove it because it locked up the Phone app when I clicked on it. Fortunately, I sync with MobileMe, so I just removed it from the web interface at me.com.
So basically you may be forced to remove it another way (ie, from the computer you sync the phone with)
How do I remove it from the computer cant seem to figure where or what i sync my contacts with on vista Thankssss

Edit:
I should add this was on both AT&T and Verizon iPhones, both jailbroken and stock.