To pair the 360 remote hold down the 'TV' button and '0' button together until the Standby button starts to flash. If the remote appears to have stopped working make sure the the power saving mode setting is on Fast Start
The Service you do for others is the rent you pay for your room here on Earth - Muhammad Ali
"Make sure you are near the media box.Pair the remote control with the media box by pressing and holding the TV button and the NUMBER 0 button simultaneously for 10 seconds.If the pairing is successful, the light on the box flashes once and a message appears on the screen."
Set your box's power mode to fast start which should stop the remote from losing its pairing:
Home>Settings (cog)>System>Standby Power Consumption > Fast Start
or Press and Hold the mic symbol and say "Settings" then use the arrows and OK button to navigate as above. (System>Standby Power Consumption >Fast Start)
Noticed you'd tried pairing again already - try removing the batteries from the remote and re-inserting and re-doing the pairing. If that works you can also try resetting your 360 (System >Factory Reset). You won't lose any settings etc. but it should re-pair the remote properly.