I actually think this is something GitHub should help with. When you flip a repo from private to public, it should prompt you asking if you want to wipe out all the version history first.(essentially create a brand new repo in the background)

Seems like far too common a mistake and something they could help fix once and for all.