I don't know any details, but AFAIK they got lucky because the licensing company for LOTR, Middle-earth Enterprises, had been in a tug-of-war between media giants like Amazon, Time Warner and (later) Embracer for years when they struck the deal. I assume it was much easier for the company to greenlight relatively small deals for niche games with a smaller partner like Daedelic.