You're right. There is a possibility that no candidate will emerge as the true majority winner in the sense that the candidate beats each of the other candidates by a majority. This was a possibility recognized by the creator of majority rule, the Marquis de Condorcet, who was an 18th-century philosopher and political theorist who proposed majority rule but noted that it wouldn't always produce a majority winner.
If that should happen, then there would have to be a tiebreaking mechanism. One way to break the tie, perhaps the simplest way, is then to apply first past the post. You wouldn't have to have voters re-vote. You already have their ballots, so you would just take the first-past-the-post winner. There are other tiebreaking methods that could be used as well.
The point I'd like to make, though, is that from what I understand of the Canadian situation, the possibility of not having a majority winner is quite remote. Practically speaking, I believe you would almost always have a true majority winner emerge for each seat.