Decentralized transactions between two decentralized currencies Currently, bitcoins and namecoins are implemented using the Bitcoin protocol. And there might be several reason for new block chains to appear, but this is not the subject here.

As far as I know, Bitcoin was not designed with ‘cross-currency atomic transactions’ in mind.
For example, as of today, one cannot exchange bitcoins for namecoins using the Bitcoin protocol itself.
A partner might be willing to trade, but some trust is required: who will send their coins first ?

Given that the main interest in Bitcoin comes from its decentralized nature, accepting the need of a third party to arbitrate exchanges between two such decentralized currencies is rather disappointing.

Is there anything to be done to allow ‘decentralized cross-currency transactions’ using the protocol itself (scripts maybe)? or could it be achieved with some simple modifications to the protocol?
Is this theoretically impossible under some specific conditions?
I have actually been working on this exact problem. My motivation is to achieve a slightly different effect than what you're asking about.

I'd like to be able to "move" some Bitcoins to a different hash chain, allow them to be exchanged in that hash chain (as Bitcoins), and then I'd like the final holder to be able to "re-import" the Bitcoins back into the regular hash chain. The goal would be to create "side-chains" with faster block generation times useful for smaller transactions. (They could also 'expire' after a few months and be forgotten, reducing the size of the permanent hash chain.)

But the basic problem is the same. You need the legitimate holder of some Bitcoins to depend on a fact verifiable only outside the Bitcoin hash chain. In both cases, the existence of a transaction in another hash chain. (In my case, a Bitcoin hash chain but not the Bitcoin hash chain. In your case, another currency's hash chain. But the principle is the same.)

The problem is that the Bitcoin design requires every client to be able to validate every transaction, as they must track coins all the way back to their origin to confirm their validity. This means a transaction must be verifiable with only information every client should have -- and that means only information in the Bitcoin block chain.

A third party could put this information into the Bitcoin hash chain. But you'd have to trust that third party, defeating the point.

I have thus concluded that no solution is possible, unless someone has an idea that breaks my assumptions. I hope that will happen, but I am not clever enough to think of it.