Je správně nájemní voják, nebo nájemný voják?

Setkal jsem se víckrát s oběma tvary. I v odborné literatuře.

Nenašel jsem odpověď, ale čím víc o tom přemýšlím, tím víc jsem v tom nejistý. Od slova nájem a nájemné. Voják je sice rodu mužského, ale nevím, zda je to v tomto případě rozhodující. Přídávné jméno se tím nemusí vždy řídit. Máme i třeba nájemní vztah, nájemní byt a ty jsou taky rodu mužského.

Žoldák se najímá, je najatý. Nájemní jako námezdní voják? Ale může být i námezdný. Nájemný, nájemní od nájmu? Hlava mi to nebere.