vpn is probably the best way forward. however, you may have some difficulties depending on how you do it.
my recommendation would be to use hardware vpn devices and create what are known as site to site vpns.
the other way to do it would be to just use windows xp machines to initiate and host the vpn connections - simply a case of setting up and incoming and outgoing connections on each machine. you would then have to have some kind of routing scenario (you could probably bodge this using internet connection sharing on the vpn dial up entry)
there are also probably some 3rd party freeware apps for setting up vpn servers.
the problem you will likely encounter is getting the traffic from one xbox to another.
each site must be on a different network id - ie you cant have 192.168.0.x/255.255.255.0 at each site. then comes the problem that you will now unlikely be able to browse across the networks and will have to be dependant on being able to enter IP addresses in the software with which you plan to access the xbox. the reason i say this as i once tried to get an xbox running xbmc to read media from a pc on a different subnet and had a mare before giving up (may have been an off day (IMG:
style_emoticons/default/smile.gif))
if you only plan to get pc to xbox access then you shouldnt have any major issues using a vpn. if you want help with the nitty gritty then let me know if you want to invest or do it on the cheap and what you need to have access to and from and across what type of networks