Have you seen http://www.memset.com/ (or .co.uk)
I've not used them, but tempted. They aren't a co-lo, but given the prices, maybe you could simply get another box and save the taxi fare? They host smoothwall.org, which may or may not be a recommendation. > Can anyone suggest a way that I can check my existing linux box to > determine how much I am practically using at the moment? ifconfig look for the line RX bytes:12967926 (12.3 MB) TX bytes:2434013 (2.3 MB) for your relevant nic card. Monitor it over a couple of days...