This is something I've been thinking about for my Linode. I'm thinking about reselling hosting on the box - though the problem being is how to account for bandwidth transfer.
I assume you are running apache (either 1.3.x or 2.x), in which case there are a couple of tools you can use in order to identify which apache virtualhosts are using what bandwidth.
If you are running apache 1.3.x (I'm running 1.3.27 on Debian), you can use mod-throttle (
http://www.snert.com/Software/mod_throttle/). It's intended to be used to limit the bandwidth used over a period, though it can display (per virtualhost), what bandwidth has been used. I've even written a PHP script that parses it's output for use on another page - such as the 'overview' page in the Linode members area. Having done some testing, mod-throttle is very accurate in it's reporting - it reported the size of a file I downloaded to within 0.1kb.
If you are running apache 2.x, there is mod-watch, written by the same guy. This is a much more powerful version and allows you do even graph bandwidth at various times of the day. Note that I've not used this - though if mod-throttle is anything to go by then it'll be good.
http://www.snert.com/Software/mod_watch/
As you've found, the problems arise when you come to monitoring email, ssh, ftp etc. I looked into this a while back, and came to the conclusion that there really a way to do this. I found a stats program called modlogon that appeared to go some way to providing a solution - parsing exim/proftpd logs, and tallying them - though I can't seem to find the URL now
Obviously I'm not aware of all of the circumstances surronding your problem, though I'm tempted to go with the opinion of SSH traffic being so neglible that it's irrelevant, and (assuming that anonymous FTP is disabled) adding a further 10% to whatever mod-throttle etc says to account for FTP and exim usage. Of course this is not an ideal arrangement, since who's to say that the customer doesn't use email lots and very little www transfer.
If anybody else has any thoughts/comments/solutions to the problem I for one would be glad to hear them.