Have you checked the "whois"?
Have you "ever" actually owned the domain names?
Many of the cheap deals that one sees around has the host as the domain name holder to tie you to their services and you cannot transfer the names away and, I'm guessing here, maybe not even cancel names.
If, IF, you were the registered owner then you most probably have a very good case however you must first check out exactly who all the names were actually registered to since a solicitor will want to see factual information not presumption.
If you're not the actual registered owner then you have a lot of in-depth thinking to do apart from finding a reputable host and name registrar that do not mess about like this!
The market's very competitive and they definitely won't want to lose any potential business therefore they may be bluffing, sound them out.