Michigan J. Frog originated in 1892
His little music hall performances are rather dated for 1955 (when the demolition guy finds him) and especially
2056 (when the disintegration guy finds him), but they're perfectly current for 1892 (the date he was hidden in that building before the demolition guy found him). He doesn't update his songs or costume for either of the times we see, so it seems unlikely that he would have done so for the person in 1892. Thus, this person, whoever they were, didn't just find Michigan in yet another building, where he was hidden by yet another unfortunate soul another century earlier. Rather, they were the first person ever to "find" him (in a remote corner of the rainforest? A meteorite impact site? Who knows?), or, my theory: they created
Michigan J. Frog was created by the devil to sing to make people who found him miserable.
When the demolition guy found him, he expected to be rich, but the frog wouldn't sing to anyone else no matter what he did. It ends up making him homeless (he bought a theater for the frog to perform in front of everyone but it failed), and when he's on the bench, the frog's singing lands him in a psychiatric hospital. Eventually the man seals him away and he survives the next hundred years where the disintegration guy finds him.