Everytime I sync my iPhone, any contacts I have deleted from my iPhone reappear, like the old contacts are added back. New contacts remain.
Because your last backup has been used when you plug in your phone. Try moving the backup file to another folder (just in case you may need it), then delete the contacts you want to delete on your phone.
Once you got rid of the contacts you wanted to remove, create a new backup.
This should stop adding the contacts when syncing.