As for the never-Democratic counties, I'd assume one should look in Utah, Wyoming or Idaho, the three most notorious GOP bastions in the country. Or look in the Texas Panhandle where recently the counties have been going 80-90% Republican; in fact, King County, TX delivered John McCain with his strongest victory in 2008, I think it was like 93-5% and Obama only received 8 votes in the entire county. Of course, you also can't dismiss some counties in Oklahoma where not one single county voted for Obama in 2008. Look closely at the three counties in the Oklahoma Panhandle as well: Cimarron, Texas and Beaver counties. I couldn't fathom living a county named Beaver LOL
That would be quite interesting to know, i.e. the two counties that have the longest streak of voting Republican and Democratic. I believe I read somewhere where Elliott County, Kentucky has the longest streak of voting Democratic, which is kind of ironic seeing as how it's in Appalachia.