Currently, 9 states hold the record for longest winning streaks for a party. Utah, Idaho, Wyoming, Alaska, North Dakota, South Dakota, Nebraska, Kansas, and Oklahoma have voted for the same party since 1968. Arizona had the longest streak until 1996 when it voted narrowly for Bill Clinton; Virginia and Indiana were also part of the 1968 streak till they both voted for Obama in 2008.
So the question is, will any of these states be able to surpass Vermonts 104 year streak of voting Republican (from 1856-1960), or Georgia's 108 year streak voting democratic (1852-1960 if you don't include the 4 years it didn't vote because of the civil-war)? North Dakota and South Dakota have been competitve in the past (barely in 2008, but South Dakota almost voted democratic in 1972 and 1976), while Alaska has been consistantly trending towards the Democrats for 3/4 elections. Wyoming was kind of close in 1992 because of Ross Perot, while Utah was sort of competitve because of Mcmullin. Most of these states are also going to be considerably more diverse in the future, so that could be an effect in future elections. If I had to say which states had the best chance of reaching this streak, it would be in this order (most likely to least likely): Idaho, Wyoming, Utah, Nebraska, North Dakota, South Dakota, Oklahoma, Kansas, Alaska.