It's been a while, but I finally found the reason why my volume commands sometimes work and sometimes not;
If the TV is already on while the MD starts, the volume works. If the TV is off while the MD starts the volume commands do not work (but everything else does).
I checked the ruby code in the template. During intialization, in the InitVolume function, it does something clever. It tries to retrieve the current volume from the TV, even turning the TV on and off again if necessary.
My guess is that my TV (an 26LV5500) doesn't like that, gets into some strange internal state, and no longer responds to volume commands after it has been quickly turned on and off again.
I placed the line "@volume = 10" at the start of the InitVolume function. That way the function assumes the volume has been retrieved successfully, and doesn't send any commands to the TV. This works, but I'll see if I can find out which part of the InitVolume function is actually causing the problem.
For now it looks like a problem with my TV's software, not with the template.