My first piece of text is related to Companies House registry, you are right.
HMRC doesn't have publicly accessible companies register...
...However I couldn't find them in the publicly accessible register neither here (the service cease on 31 of March 2013) nor here.
go here
https://customs.hmrc.gov.uk/msbregister/search.do?type=newSearchthen in "Money Laundering Regulations registration number" field enter 12713897 (I took it from their site, you quoted it as well)
in Postcode type EC1N 8SB
click search
then you will see a record but for another spelled company "Coin floor" (with a space, not Coinfloor) and with another address.
my screenshots from the previous post show it clearly
HMRC service doesn't work for me, don't know why. But if you were able to find HMRC money service registration, this just proves that they do have a valid certificate. They registered with HMRC at the same time as they changed their name, hence HMRC shows the old name.
HMRC website says (from your screenshot) Date registered: 01/06/2013
Companies house website says: Date of change 29/05/2013 Previous Name COIN FLOOR LTD
Probably they filed for both name change and money service certificate simultaneously.
"Trading address" for the bureau de exchange doesn't have to be the same as a company registration address. Company number and money service certificate number are different things altogether. Nothing shady here.