I'm glad to see the softlinks mentioned it, but I'm surprised to see that (to me, at least) the most obvious "trick" answer isn't there, despite actually being a correct one too.
What about Alaska?
The eastern boundary of the southern panhandle has an easternmost point, at which point it curves back with plenty of boundary to make for a suitable answer. (That's the "trick" I was checking for; I wasn't up on my geography enough to know by heart if the boundary came back.) There's only about 10 or so kilometers of land boundary (near Hyder, Alaska and Stewart, British Columbia, according to Google Maps) before the rest is water, and I don't know if there are bridges, but hey - nobody said you had to drive on roads.
(edit after the fact: oh, and there are a bunch of other places where the boundary jigs back toward the east on its way northwest until it gets to the meridian border.)