Well, as I said I'm still reading the HoA spoilers thread and I just read this you should have commented to death:
This is slightly a tangent, but here is a relevant chunk from the Warbreaker Annotations. As this won't be posted for months, I'll put it here as a sneak preview.
Chapter Thirty-Two
"This whole scene came about because I wanted an interesting way to delve into the history. Siri needed to hear it, and I felt that many readers would want to know it. However, that threatened to put me into the realm of the dreaded info dump.
And so I brought in the big guns. This cameo is so obvious (or, at least, someday it will be) that I almost didn’t use the name Hoid for the character, as I felt it would be too obvious. The first draft had him using one of his other favorite pseudonyms. However, in the end, I decided that too many people would be confused (or, at least, even more confused) if I didn’t use the same name. So here it is. And if you have no idea what I’m talking about. . .well, let’s just say that there’s a lot more to this random appearance than you might think."
From BS dated 19 october 2008.
So.... I think it is ok to have different lines of thought in theories, but that this clearly points to him being the same character in every world, so he must be travelling from world to world. Taking into account that every book happens in a different "universe chronology", he can be in every series being the same man.
And he hasn't to be powerful in all of them. For example, if Elantris is the "oldest" (in universe chronology) story, he could just be a beggar who later in the series obtains his power. Same if Mistborn is the oldest. He could just be a skaa and later on he got his power to travel. It is pretty obvious that Warbreaker is not an old story in BS universe (maybe we will find Scadriel travellers landing in Warbreaker's lands?)
I really believe we will know of him later on, and that the one story we hear from him being able to travel through worlds will be one of the "oldest" one.