The way I like to work registration is that it is more like a very high tech version of a passport and ship's log. That is, the "universal" convention is that when you pull into a starport (C class or higher D and worse being really non-ports and all A and B's do this everywhere) the owner / captain or designee has to present the ship's registration "papers" to the port officials. They enter the date, time, etc., that the ship arrived, departed, got maintenance, who's on the crew, and can check where the ship has been in the recent past. It has a complete record of the ship's movements from construction.
This is like one type of official log the ship must have and must correctly maintain. Failure to do so results in anything from a serious fine to impounding the ship until everything is cleared up.
The record is difficult to forge since many worlds use unique means of entering their data on the forms in the record. A forger would have to have the ability to produce not just a wide array of entry types, but the record would have to be chronologically and astrologically accurate as well. There might also be advanced methods used that can accurately determine when entries were made by other means sort of like carbon dating something; again making forgery difficult or impossible.
You pull in and have no entries for months and you generate instant suspicion on the part of port officials.
It is the sort of log commercial truck drivers maintain or ones that an airline has to keep on each airplane. This way there is less need to try and match the ship to the log and try methods to mark it that could be circumvented.
Additionally, each port keeps files and records in their own database that match the ship's log. So, if the ship comes in again the record is automatically checked for anomalies against previous versions to catch doctoring or forgeries. Many systems (A and B ports in particular) also forward this information to other starports in effect creating a record that is everywhere of a particular ship's movements, maintenance, crew, you name it.
This sort of record / log would be much harder to forge, much harder to alter, and really keeps the sort of information that is relevant to port authorities, customs officials, and governments.
If a ship skips on payments it isn't going to be long until it finds that going to any starport that checks logs will result in arrest and confiscation of the ship. A pirated vessel would be better chopped up and parted out in many cases. Otherwise the crew would have to find someone capable of creating a completely new forged log for it going back maybe as much as 20 or more years and then have this log inserted into the database so that it can spread itself (assuming no one notices) like a virus until it is widespread sufficently to allow the ship to assume an new identity. That would be difficult and very expensive I would think.
Of course, if all you operate out of was low end C ports along with D, E and X types you might get away with a long period of no checks. That would mean having to do your own maintenance, refuel off gas giants or unoccupied worlds or satellites, and staying 'under the radar' of officials at all times.