Not saying you are wrong, but your mortgage company or any other loans that you use your property for collateral essentially put a lien on your property and you can't transfer said property until they release that lien. Maybe there is different lien categories? Might vary from place to place as well?
They do this sort of thing with vehicles and other registered non real estate property as well, but I suppose there can be differences in how it works with certain things
Add: I guess one thing that is different is with most the situations I mentioned the owner agreed to said lien in documents they signed when they placed the property as collateral for whatever reason, where the situation in OP and what some have commented on is other way around, customer took advantage of someone's services to the property yet did not pay for that service. Had you made them sign some contract documents and included lien paperwork in those documents before proceeding with the project - that may be similar situation to what the lenders do and has no definite expiration on the lien? But the lien should be released by the contractor when the rest of contract is fulfilled as well.