Brand the mage with a 2-way transmutation circle to seal the pact
While the transmutation circle created to summon the demon is one-way and in the total control of the mage, this second transmutation circle can be opened by either the demon or the mage using either one of thier powers, and it is forever burned into the flesh of the mage so that it can not be easily removed. This way, the mage can open the link whenever he needs to access the demon's power, but the demon can open the link whenever he needs to check up on the mage to make sure the mage is honoring his part of the deal.
If the demon ever opens the link to see the mage is not honoring the deal, he can use the link as a conduit to project his power through to punish the mage. Since part of the question is about enforcing the contract, the demon has a vested interest in NOT giving the mage a transmutation circle that can just be thrown away when the contract stops being in the mage's best interest. By making it a part of the mage's body, the demon is guaranteed oversight over the deal.
As a side note: 4dam's Devil's Mark answer has some very good ideas about stuff you can do to make a branded character more interesting, even if it does not actually answer the core of the question about how to make the contract enforceable across realties. If it were me, I would work some of those ideas into this such that the mage might be able to figure out when the demon is watching when the laws of nature around him start to subtly shift.