You said almost all of them are first-timers. Is that based on something objective, like cookies? You could redirect any suspicious visitors to an "I don't like your face" type of page containing an obfuscated e-mail or something that only humans can read.
The conditions would have to be:
-- Request for certain specific pages
-- No referer
-- No existing cookie
No matter what they do they'll be taking up bandwidth. But you can redirect them to a page that takes up only 1 or 2K instead of the full size of the page they're aiming for. (Don't know about you, but I have a steady stream of robots heading straight for my fattest page. I finally threw in the towel and reconfigured it so nobody can get there except via a shorter gateway page-- which has the name of the old long page. So far it's working.)