No, contacts are not part of the phone app's data. They are handled by an app called "Contacts Storage" (Settings > Apps > All and you'll find it there). Clearing data for that should erase everything, so make sure you have everything backed-up before trying that (I'd be tempted to "export" them from the People app as well as having the Google backup, just to be safe).
Is there anything different about these contacts? Specifically, are these contacts which you'd backed-up to GMail and had then deleted, or are these other contacts (phone only or stored on the SIM)? Check Settings in both Phone and People and see whether they are both set to show all types of contacts, in case you have one of them set to only show some types.
Also, have you tried the trivial thing: rebooting and seeing whether they disappear?