According to the 4 levels of PCI certification, which level are you guys currently following?
You said that you've done network vulnerability scans, what about an annual SaQ? When it asks you if you've secured 'credit card holder data', just replace that with our 'Bitcoins'. lol.
By volume we're 3 or 4 but we've only been live for 22 days. Also we're not taking credit cards but adhering to their standards regardless.
We've done the SaQ and treated the Bitcoins as credit info like you suggest. We're treating ourselves as level 2. The next step up is on site audits for level 1.
Obviously these are huge businesses like Amazon.com etc but we're willing to go through on site audits etc and would prefer to given some time.
PCI scanning and putting a seal on your website from Trust Guard, Verisign or McAffe doesn't make you immune to all attacks but it is one step towards a safer exchange and something we should have done a long time ago.
At least you acknowledge the uselessness of a seal. Really, it shouldn't be a selling point - every idiot can run nmap/nessus/acunetix ..
Luckily (from Camp BX):
We were tested for >1,000 known vulnerabilities specific to our platform and services by McAfee Secure
Means you're obviously 43x as secure as they are.

In all seriousness, publishing a report of a manually performed pentest or source code audit (perhaps with selected individuals) would be useful - this is 99% marketing talk like TrustGuard/McAfee sells it to their customers. But it's good to see you're at least informing your clients...
We acknowledge that this is far from a silver bullet. Regardless there are probably sites operating that would have or would currently fail these tests. This clears up the major vulnerabilities and I'm happy that we didn't have to make any corrections when we received the audit. Our existing security was sufficient.
As I said before this should be a bare minimum and we have more to come.