They won't leave. Despite the stadium issues, I don't see moving a successful franchise in the 14th largest market to an unproven (or previously unsuccessful) city.
You may want to say hello to the Baltimore Colts, Oakland Raiders, Los Angeles Raiders, Houston Oilers and Cleveland Browns... who all moved purely due to stadium issues.
Houston was the 4th largest market when they lost the Oilers to Nashville, Oakland was a far smaller market when Al Davis moved the Raiders back from L.A. and Indianapolis was a smaller market when Irsay uprooted the Colts. Also, the LA Rams moved to the much smaller St. Louis market because they couldn't get Orange County to upgrade facilities.
Stadium issues have driven pretty much every team relocation in the NFL for the last three decades. Honestly... Baltimore, St. Louis, Cleveland and Houston have all had teams leave in the last three decades and were all granted new franchises. Which tells me it was never an issue of fan support.
I feel sorry for Vikings fans that the legislature has decided to stick its' collective head in the sand regarding the Vikings. They should've took care of the Vikings first before the Twins, as the Twins options for relocation were much more limited. A three to six month window exists to get something done and with LA in the mix... Zygi Wilf holds all the cards. Which means Minnesota tax payers are going to end up with a much worse deal now than if they'd taken care of the Vikings five years ago.