While it depends on the country, you don't have to be a bank to be regulated in the UK.

For example, the Financial Services Authority says you need to be registered for accepting deposits or issuing e-money: http://www.fsa.gov.uk/Pages/Doing/Do/index.shtml

I have no idea whether this is simply or cheap though...