1. TuorTúor becoming Immortal is only a supposition, and not fact.
So, TuorTúor becoming immortal could be true, but could also just be something Noldor in MEMiddle-earth believed without definitive proof of truth, as per Tolkien's emphasis. Since this information is supposed to be coming to us from the beliefs of the NoldoNoldor stuck in MEMiddle-earth and the trip to Valinor is a one way trip, accurate knowledge transfer from Valinor to Middle-Earthearth presumably doesn't happen.
If the myth is, in fact, untrue, one source of this belief could be the rare case of Glorfindel's return to MEMiddle-earth. One would have to make multiple assumptions (fortunately, all of them things debated but not settled by Tolkien himself) - that Glorfindel of Rivendell was indeed a re-embodied re-incarnation of Glorfindel of Gondolin; that Glorfindel returned to Middle-Earthearth sometime in the Second Age; and that while Aman does not stop mortals from dying, it can extend their life to the fullest, so that TuorTúor was indeed still alive at the point when Glorfindel left the Blessed Lands - and that this was the piece of news that gave rise to the idea of Immortal!Tuoran immortal Túor amongst the NoldoNoldor Eldar and Edain in MEMiddle-earth.
2. Luthien'sLúthien's exception is referred to in similar terms as Tuor'sTúor's exception
In the primary story of Lúthien and Beren, LuthienLúthien is allowed as an absolute exception to divest herself of 'immortality' and become 'mortal' — but when Beren is slain by the Wolf-warden of the Gates of Hell, Lúthien obtains a brief respite in which they both return to Middle-earth 'alive'.
Though of course, Luthien'sLúthien's fate is considered more 'factual' than Tuor'sTúor's. Presumably the difference is that Luthien'sLúthien's death, return and final death was something the NoldoNoldor in Middle-Earthearth could corroborate - and if Glorfindel could share news of the life of TuorTúor, he could certainly convey the news that LuthienLúthien had not returned to the Halls of Mandos after her demise.
4. The Reason for LuthienLúthien and Beren being allowed to come back to life is given
It doesn't definitely answer why TuorTúor and LuthienLúthien were given special dispensation to join their spouses' ultimate Doom (and why the solution was different for both couples), but we can assume this was as reward for folks whose love (and resultant procreation) was an important part of the Divine Plan, instead of the 'punishment' that eternal sundering might have been to them.
Rob answers the 'Why was Beren in the Halls?' part of things very correctly, and also explains how ManweManwë was able to confer the choices to LuthienLúthien. The spirits of Men seem to make pitstop in Mandos before leaving the confines of the World as is their Doom.
It was to the Halls of Mandos that the spirits of Elves and Men were gathered to await their different fates**, and so Mandos was given its name of the Halls of Awaiting. After a time, the immortal Elves could be re-embodied, and return from the Halls to their kin in Aman. Men had a different fate, a fate which, even among the Lords of Valinor, only Mandos and Manwë truly understood. No one, however, not even Morgoth could escape the Halls without Mandos' permission. [wiki src][wiki src]
Beren extended his stay on Luthien'sLúthien's request.:
And Mandos was able to gain counsel on what to do from IlluvatarIlúvatar himself.
"ManweManwë sought counsel in his inmost thought, where the will of IluvatarIlúvatar was revealed."