This posting is older than 6 months and can contain outdated information.
1st: I lowered the resolution of my display and it seems to have helped.  EyeTV is better (though still not quite 100%), and fullscreen movies in iTunes are fine.  For those running old Mac Minis, the resolution I selected for my LCD TV display is 1024x614.  A resolution close to that should work alright.
2nd: I tested the issue a bit more, and it does seem to be worse with Applescript-derived RB menus than with the normal RB menu.
3rd: just a couple notes for Felix after all this experimentation with screen resolution:
- While you can control the size of the normal RB menu with the slider in the preferences, the size of the Applescript-derived menus is apparently static.  Probably not worth putting much effort into changing, since it will so rarely be a problem (only on screen with vertical resolution of less than 550 or so, which isn't many these days - it looks fine with my 614 vertical pixels); but I thought you should at least be aware of it.
- More importantly, because it's not just an aesthetic issue:  the RB preference panel can be problematic on screens with a vertical resolution of less than 640 pixels.  Specifically, that is the approximate height of the "custom actions" sheet within the "behaviours" tab.  At my resolution of 614 vertical pixels, I am unable to press OK to dismiss the sheet.  You might want to make this sheet a bit smaller, so those with underpowered computers can go down to 800x600 resolution.