> In fact using bitcoin would make it far easier for someone to start tracking anyone who used the service by tracing back the transaction chain from the wallet of the hosting provider.
Assuming all transactions will go to one address or come from "traceable" sender addresses is a bit presumptive.
Why not let the users sign up for the service (over Tor or whatever), then generate a bitcoin address for them to send BTC to? Then every transaction has a new address.
Besides that, there are a ton of ways to keep it anonymous using bitcoin.