This is going to be opinion based answers and only EllisLab can give you the correct answer - so ideally you'd need to contact them to confirm.
But you can use a license number for a single site, so a duplicate use of that license would be officially a breach of license. But only the license holder/owner can state which is the valid licensed site - it shouldn't be a case of first use.
So if you were to ensure that any notes attached to your EllisLab account and license purchase referred to your new client's website, not the old one and you made it perfectly clear in a formal letter or email that their version of ExpressionEngine is illegal and not formally licensed with polite instructions as to how they should obtain a license.
If they were to try to contact EllisLab to transfer the [now invalid] license to their own account, EllisLab would confirm with the account holder (you) first, and you would be able to explain the situation and deny the transfer.
If you purchased the license with an account in their name, you're stuck!