Deleting contacts Not listed

They must be in contacts somewhere. Try playing with the view options

 

Have you rebooted since removing the app? If so, one thing you could try is to reinstall app and see if it has a way of blocking the contacts sync - it might then delete the currently synced contacts.

Another option after reinstalling it would be to go to settings --> applications and pressing clear cache and / or clear data buttons.