I guess this would depend largely on your lease agreement terms, but to Mitel the licenses are not tied to specific phone, but to the application record of the phone system itself.
I have a real problem with this demand from your vendor, unless it is specifically laid out in the terms of the agreement. A refurbished 5312 is about $50 and a 5340 $80-$100... Even new the 5312 is about $180 and the 5340 has been discontinued for several years and replaced by the 5340e which is around $250-$300 new.
Your phone system and those licenses are quite ancient as well, that licensing model was phased out a while back, like 7 or 8 years ago roughly...
Honestly, I don't know how much they are going after you for, but if it is a really big amount I would try to negotiate a settlement that is agreeable, or contact an attorney.
DISCLAIMER: This is my personal opinion and information from some quick Google searches. Legally it would depend on the terms of your lease and it's termination conditions... but in this case I would say you have likely paid for your equipment 10 times over, and you may have a legitimate legal grounds to get out of this. Most leases we see are not perpetual, and have a fixed term with a $1 buyout at termination of the lease, so I could be way off base here too.