I doubt that there's anything you can do to your Xbox - the video chip will almost certainly always output overscan lines at the top and bottom of the screen, but even if you could change that you'd have to fiddle with register settings in the chip to effect the change. In any case, I suspect that's what XBMC is doing, and as you saw that made no difference, because some of the overscan lines always remain.
It would be worth checking the manual for the VCR, and trying all of the menu options on the VCR to see if any of them have an effect. Unlikely, but worth ten minutes fiddling before you spend any more money on a solution that might be no better. It would also be worth trying a different VCR - I've never seen a VCR do what yours is doing to that extreme extent.
While an external RF solution should reduce or get rid of the overscan problem better than your VCR there's no guarantee - and as Tidyboy89 suggests the output quality with RF modulation is rarely better than average. If your Xbox is a 1.5 or earlier and you have a computer monitor then the VGA solution might be a better option - you need a VGA BIOS, an external cable (DIY instructions
here, or buy one like
this) and a monitor that supports Sync on Green. If you can get it to work it will certainly be better quality.