I have been thinking of going in to Bitcoin webhosting myself, and thank you for the heads-up.
Bitcoin is not anonymous; only pseudonymous. If they are not using mixers or coinjoin, you can try coin tainting to black/greylist the spammer's coins. To do this, you would need to ask for a refund address so that you can safely return the coins (they will start mixing them; making assumptions will result in lost coins).
Black-listing is bad for Bitcoin in general though because it hurts fungibility. That said, encouraging coin mixing makes Bitcoin safer for all users because block-chain analysis becomes more difficult.
Do these users not need contact information to sign up? You can do confirmation e-mails like mailing lists if you do not already do that.
They are using free email address. We do receive email confirmation, but again the email addresses are disposable.
Maybe you should require phone number verification via SMS or a phone call? Most legit customers have landlines and/or cell phones.
It doesn't need so troublesome, just change a web hosting business