Before someone says: "Hey, colored coins can move Fiat..." I assure you that so far everyone talking about them has only suggested holding an IOU in colored coins, which is simply not good enough for our needs. Any attempt to have some kind of bank fulfill an IOU is to make a CPOF again.
But we know that the actual value of Fiat can and already is held in software now! Most of the planet's Fiat DOES exist only as digital currency, and moves just fine through networks like Wire transfers, SWIFT, SEPA, and ACH. -So if those networks can get access to the value of nationalized currency, then we should be able to as well... As an example, think of doing an ACH transfer to a software client, and from there it exists only in your online wallet as fiat credit.
If you take out the decentralized fiat requirement then the system can be built fairly easily. It is just a technical problem. We could end up with a P2P version of localbitcoins with some 'real-time' trading functionality, where escrow is used to enforce trading rules.
But as you say, we must have this instant-trading facility for it to be a successful replacement for MtGox. To do this we must have some cryptographic representation of fiat, so it too can be kept in escrow and traded like Bitcoin, quickly.
Real-time trading does not work if I have to keep checking my bank account to see if Bob has sent me the $10000 or not. Which can take days. Even if it takes an hour, it is too slow.
So for instant trades we need to store a fiat balance somewhere. How can that be done without requiring IOUs and trusting some third party to keep my money safe?
The only solution I see is in having a distributed set of IOU issuers who deal with fiat. Trust cannot be avoided, but at least with a federated system you can spread the risk, and probably chose to only hold onto IOUs for a small amount of time.
So if we have decided that we need to represent Fiat as some crypto IOU style token (a c****ed coin) then we can alter the original requirements so that it no longer mentions fiat.
I would argue that we need:
1) A P2P real-time trading platform for crypto currency. (no mention of fiat)
And completely separately,
2) A lively ecosystem of dealers of IOUs that allow you to get fiat in and out of the P2P platform.
I would also argue that a nice solution to 2) could end up looking like Ri**le, without XRP and where the project is entirely open source.