I went to the Videoself on Bishop. To rent from the machine, you need a membership card, and in order to get that, residency is required.
Now, with Redbox in the USA, only a credit card is required. It does ask you for the zip code of the credit card; I don't remember if a Canadian postal code can be entered. Redbox automatically charges you $1/day, and if you keep it past 25 days, the DVD is yours. That's how they handle losses.
It's just as well. There is plenty of stuff to do in Montreal. My hotel just happens to have a DVD player in the room, so just wanted to try that out.