I absolutely agree with cnvi. Let me elaborate a little:
First: what Google finds relevant is not the main question. The main question is relevance for the intelligent human being. For a visitor looking to book a hotel in Toronto, links to Paris reservation sites are completely irrelevant, let alone “travel to China, safaris, sightseeing in Rome, etc”. If Google finds relevance now because both "Toronto Hotels" and "Paris Hotels" have the word "Hotels" in them, it should (and probably will) in some future find a way to correct that error, and all your efforts are in vain.
Second: the word “Toronto” is just as relevant to Google as the word “Hotel”. And “Toronto” sure is far more relevant to your visitors. So why not exchange links with Toronto related sites. Make a directory about businesses in Toronto, restaurants, bars, museums, anything of interest to your visitor. These businesses would be all to happy exchanging links with you, because your hotel guests may want to visit their bar (etc).
Third: Sure Google is “Lord of the Internet” now, but gathering quality links for long-term rankings is a time-consuming effort. Even Google can go down and loose to a party that serves more relevant search results. If your guideline has always been relevant for the visitor, you win, if your guideline has been what is relevant to Google, you loose.