Have most states had a third party win them at least once?

[Nym90]

Well by definition most have, since most=a majority. But not by much of a majority.

[Nym90]

By definition the Republican Party is a "third party" since they challenged the Whigs and Democrats in the mid-1800's.
So, technically every State has gone to a "third party".

Perhaps, although since the Whigs no longer exist, I'd say the Republicans replaced them as the new "second party". While the Whigs were still in existence I would agree with your definition.