Companies House gives your company a number when you register with them. Any reason why they couldn't use this? God (all hail his noodly appendages) forbid that two government organisations actually exchange one item of data though. EDS would probably charge them £1b to create a system. I'd offer to do it with a memory stick and a 10 minute walk every day. And only charge them half as much :-)

Yes, not all businesses that deal with HMRC are registered companies. There are also sole traders, partnerships etc - all of which have to pay tax, and VAT if their turnover is high enough.