The police officer sounds like a cool guy, but you have NOT solved the problem.
You need to start verifying the identities of depositors and people withdrawing money from your exchange like Mt Gox and other operations do. Not only is this your protection against being an exit from the fiat system for criminals, but the law may sometimes require it too (depending on thresholds, etc).
Whilst the police officer was obviously nice to you, don't take it personally if they come back and charge you with something. You clearly know there's abuse of your service and you will be expected to stamp it out. ID verification is the way to do that, so get on it.
Come on. I haven't read the entire topic yet, but are you seriously implying that his service has any amount of guilt in this? That OP has something to "solve"?
People should simply learn not to send money to unknown types on the internet without escrow. Either you verify the other party reputation or you use a reputable third party, specially for meaningful amounts.
Financial privacy should not be thrown away simply because some are irresponsible with their money.
That said, I don't doubt at all that he might be required by law not to respect people's privacy, as you say. If that's the case he doesn't have much choice anyway.
I've implemented a new policy where we require bank transfers to include the message "For buying Bitcoins".
Smart.
one problem with this is that real customers who are actually buying bitcoins, might not want such an explicit record of that fact in their bank statement.
They're already sending money to BitcoinNordic account anyway. Unless you're talking about owners of joint accounts who don't want the other owner to know where the money is going to (fishy), for everything else that matters it's already "written" in their statement what they used that money for.