I was under the impression that in the early days of the US it wasn't uncommon for US Presidential Candidates to pick their running mates from other parties and that this wouldn't hurt their chances at winning the presidency (in fact it might help bring in a broader vote).
As far as I can tell it only happened a handful of times [DeWitt Clinton (Democratic-Republican) ran with Jared Ingersoll (Federalist) in the 1812 Election; John Floyd (Nullifier) ran with Henry Lee (Federalist/Democrat) in the 1832 Election; Millard Filmore (American Party) ran with Andrew J. Donelson (Democrat) in the 1856 Election; John C. Breckinridge (Southen Democrat) ran with Joseph Lane (Democrat) in the 1860 Election ^(I'm not sure if these are different parties); Abraham Lincoln (National Union) ran with Andrew Johnson (Democrat) in the 1864 Election].
But what I did find odd is that most of the men, especially before 1940 had several parties listed. It seems that many of the candidates changed their political party for election years.
Why? And what did the general public think of this? Was the transition/evolution more natural that how it seems to me 100+ years later?
I would have a hard time trusting a candidate that went from Whig, to Republican, to Know Nothing, to Federalist.
So, the modern two-party system dates to the Civil War or thereabouts. There have been occasional third parties of national impact, and the coalitions that support the two major parties have shifted at various points, including the New Deal and the realignment of Southern whites from the Democrats to the Republicans that began in the 1970s. But the identities of the two main parties as Democratic and Republican dates to the Civil War.
The Republican Party was founded in the 1850s, rising to replace the defunct Whigs, who had themselves arisen out of the splintering of the Democratic-Republican Party, which had been the sole viable national political party after the collapse of the Federalists during the War of 1812. During the periods of transition there were still individuals who identified as Whigs, or Federalists, and there were also upstart parties (such as the Know-Nothings) who sought to make a play for national prominence but were ultimately edged out by the new parties. This is further complicated by the fact that one candidate could sometimes be the nominee of multiple parties.
Looking at a politician who was active from, say, 1824 to 1860, it would have been totally normal for him to have been, in succession, a member of the Democratic-Republicans, the Know-Nothings, the Whigs, and the Republicans.
In other times, such as during the New Deal, when Franklin Roosevelt managed to secure a coalition of working-class whites and African Americans, politicians would have changed parties based on their own interests and constituencies. For example, a business-minded Democrat who had been aligned with Woodrow Wilson might have become a Republican, and a Southern black loyalist to the Party of Lincoln might have become a Democrat.
To answer your question most directly: The transition was definitely more natural than it seems like it seems to you today. I'm trying to think of an example that does not break the twenty-year rule, but, for example, Ronald Reagan rather famously was a Democrat earlier in his life, before becoming both a Republican and interested in public office. If Reagan had been a Democratic politician rather than merely a Democratic voter, and then switched to Republican in the 1970s, that might have raised some eyebrows. But these antebellum politicians who show a lot of political affiliations were simply weathering the storm of a major shakeup in the party system.
I think Daniel Walker Howe does a good job in What Hath God Wrought of exploring many of the changes in the political world of the United States in the decades before the Civil War, if you'd like further reading.