Word of caution, test on one contact you don't care about first. I got to the B's before I thought, "maybe I should look at the results before I continue." The deletions that I had done were removing from all the groups, including gmail online. You might want to turn off syncing before you get too involved.
ps, I also had a group called Not Assigned, this was from a Export/Import from sd card.
You would think that with a Gmail account and a Google OS managing contacts would be a seamless event.