messiah - How will we know the moshiach when he arrives?

I was asked this question over Shavuot and I didn't know either, so I turn to Mi Yodeya. We are told¹ that when the moshiach comes Eliyahu HaNavi will announce him; the implication is that this is when he first arrives, not after he's fulfilled the duties of the job (gather the exiles, rebuild the temple, etc). So how will we know at the beginning, before he's proved himself, that this really is Eliyahu and the moshiach? Anybody could claim to be -- wouldn't be our first false claimants, after all. So when somebody arrives and says he's the moshiach and we should immediately follow him to Eretz Yisrael, how will we know that we really should? Will Eliyahu do something unambiguous to establish his identity, perhaps?

¹ Both of us have often heard that Eliyahu will herald the moshiach, and I have the impression that this is what we're hoping for when we sing Eliyahu HaNavi after havdalah each week -- let him show up right now with this news. This question and Scimonster in a comment point to Malachi 3:23. (According to the linked question, the Rambam disagrees with Eliyahu as herald. So I'm asking according to people other than the Rambam.)

Answer

The Gemara in Eiruvin 43 quotes the Pasuk of הנה אנכי שלח לכם as proof that Eliyahu will come at least one day before משיח בן דוד. The Gemara there also takes it for granted that although Eliyahu won't come Erev Shabbos so as not to ruin Shabbos preparations, Moshiach himself can come since all our friendly neighbors will run to help us. Although, according to Rashi there, it is possible for Moshiach to come and not be aware of it even the next day, it seems like the change of attitude will happen without a catalyst. Therefore, we will see that the Galus with all its applications will be over.

More to the point, though, is the fact that Eliyahu Hanavi is a Navi. The Halacha of any Navi is that he must prove himself to be a Navi. He will either predict something with razor-sharp accuracy, as the Rambam writes in his הקדמה למשניות or he will perform miracles. This is the criteria of a Navi.

Moshiach himself has certain requirements that he must pass. The Pasuk says about him וירום ונשא וגבוה מאד. The Gemara says that he will be able to sniff out a liar, and he'll be able to rule without witness. The Gemara relates that when Bar Kochba first rose up against the Romans they thought he might indeed be Moshiach. The Chachamim tested to see if he isמורח וודאין. He wasn't, so they left him.

The Rambam seems to say that we don't have to know at the outset that it is the actual Moshiach. When he succeeds we will know, and if he doesn't succeed he can still be a Tzaddik who tried.