A company registered in England and Wales can be strongly verified online via Companies House WeBCHeck (http://wck2.companieshouse.gov.uk). This services is probably targeted at US companies but supporting the next-largest place for tech startups (</speculation>) could be a nice touch if this grows.
You are strongly verifying that someone paid the ~$25 incorporation fee, nothing else. The identity of directors does not even get verified during the process. It does not mean much without a trading history.
