There are devs working on an automated DAC gateway that will do blockchain transactions in other cryptos. What this means is that NXT <-> ANY will be able to be traded directly using the DAC. With a little more effort, the Asset Exchange can be setup to trade ANY and when you want to redeem it, the ANY will end up in your ANY wallet.
So, decentralized trustless exchange is possible with NXT, once we get the automatic gateways. Still looking for feedback and help from the people who can figure out some details that are a bit beyond me, but I have full confidence all these issues will be solved.
ANY: can be any other crypto that we add support for, eg. BTC, PPC, XCP, etc.
Also, do you know where is the full bounty list? I'm only aware of https://nextcoin.org/index.php/board,8.0.html but I don't see anything about a decentralized exchange there