It seems the Namecoin client of the sending exchange has technical problems. The most likely reason is that they still use an old Namecoin software version. A few days ago the Namecoin network accepted BIP65. This means that old Namecoin clients cannot reliably create valid transactions anymore.
I recommend you get in touch with the exchange you initiated the transaction from, and ask them what Namecoin client version they run. If it is something like 0.3.xx then they should upgrade to Namecoin Core a.s.a.p.
Nemo wrote:I see that the coins were sent with 0 fee. Could it be the cause of the problem?
No, this is no problem. Some mining pools do reject zero-fee transactions but most pools still accept those. I just checked and sent me a few NMCs via a zero-fee transaction. It got confirmed after a few minutes by the BTCC mining pool.
Nemo wrote:And how long could it take to show at least a first confirmation?
It usually takes 5 to 60 minutes. In worst case (very rare) it is two or three hours.