There's a similar scam in europe with trademark registrations, funnily enough there are more than one operator trying this so you get 3 or 4 of invoices to register your trademark after you've registered your trademark.
Thankfully, increased privacy on WHOIS records have clamped down on these practices.
A simple fix would be to dictate, through legislation, that you can't provide a government service such as a copy of your deed at a cost substantially above the cost the government is providing it at.
Not a permanent solution, but an effective shim until regulation catches up. "Department of Hotfixes"
They are quite good at looking "official" though, and always have company names that you'd think private companies wouldn't even be permitted to use.
Given how long this has been going on, and given the EU's somewhat notorious legislative machine, it's also quite ridiculous that these scams haven't been outlawed yet.