Bitcoin does provide a great level of transaction simplicity and pseudo anonymity, but sadly Fiat <-> Bitcoin services (like ours) cannot - not if we want to be around for any length of time. Don't forget you're not interacting with just Bitcoin, you're interacting with the traditional financial system and all the requirements it imposes as well.
Our approach from the outset has been to treat our Bitcoin <-> Fiat service as requiring regulatory oversight (It was a gamble) and therefore the processes and procedures we've put in place are designed to meet that requirement - at least to the level of a 'Small Payment Institution'. For a comparison; check out the client registration requirements at equivalent companies in the same sector albeit providing traditional currency conversion services such as Transfer-Wise, Currency Fair and 1st Contact Forex. You are unlikely to find one that operates without either FSA or HMRC approval within the United Kingdom or that provides significantly less identity requirements.
As an aside; we sought FSA approval (you can read more about that here:
https://bitcointalk.org/index.php?topic=158010.0), but did not receive it because Bitcoin falls into the grey area with regards to their current definition of money - however everything we've put in place ensures that we meet this requirements when regulation becomes mandatory (I personally believe this will be in a matter of months given the exponential growth of 'Virtual Currencies' and the guidance issued by FinCen in the United States). I'd also add we still have an HMRC application still in progress.
Its understandable that not everyone feels comfortable giving this amount of information to a third party; but it's a double edged sword. Wild west business ventures thrown up in a week are likely to last as long - with a generally rougher experience and no recourse for customers when things go wrong. When we say things like we have a 'segregated client funds account' - it means just that. But all this comes at a price. Obviously, if you judge it to be beyond what you're willing to pay there are thankfully plenty of other avenues available to perform transactions (but without as nice as an experience as ours

).