"Ohio is the only state not to share a letter with the word mackerel" my buddy tells me.
Of course, I need to find out what other words don't share any letters with states. So I start hunting for a large English dictionary. It turns out the Brown corpus, included in NLTK has ~1 million words. So I whip up a python script to figure out what state-word combos pass. The code lives here.
Spoiler alert: apparently there's 38969. At least. That's just words from the particular corpus I used. Ohio is the most popular (least popular?) state, clocking in at 1085. Next closest is Mississippi, at 678. Third is Alabama with 599. Ohio doesn't have any A's or E's, so that helps.