The memory pools of each node are not synchronized, so you can't require the coinbase to include proof of containment.
If you can't trust the remote nodes at all, and you need to know the state of every transaction, you have no choice but to run a full node and do the bookkeeping yourself. For Namecoin this is likely not a big problem. You can just download a signed snapshot of the database from the same place you downloaded the software.
Hm? I'm not asking for proof related to unconfirmed transactions, I'm asking for proof related to previously mined transactions with outputs which have not been redeemed as of the completion of a particular block. This should be a deterministic product of the block-chain and identically available to every full node.
I think your solution for namecoin is a non-solution because it makes it not a distributed system. You have to trust that the data has not been manipulated in some impossible to validate way. The is also practically true of the software as whole, but only because everyone isn't actually going to review the whole thing, not because they couldn't review it. With the tree solution I described you could randomly spot-check such summaries automatically, making them much less risky.
For namecoin, It's also not a solution because knowing the complete state of the system going to be too much work for most namecoin users and it's also pointless.
I want to know for sure what foo.bit resolves to. I don't have the full history (because I don't need it and can't afford the enormous required storage) so I can't tell on my own. I ask my peers about foo.bit.
They tell me that foo.bit is 188.8.131.52 and that the last update to it was mined in block 100,000. We're currently at block 120,000 (or so say my peers). With the current pruned tree stuff I can tell for sure that it really was mined in block 100,000, but I _can't_ tell if it was updated after that since my peers could trivially by sibyl attackers. (If they lied about the chain height and just claimed we were at 100,000 I'd know because I'd notice if my clock was six months off)
If there is a commitment to the open transactions I can ask single peer for the merkle tree fragments from block 120000-199994 for the relevant open transaction (hopefully most of the tree would be the same in those blocks, reducing the data sent) and then be sure that either I got the correct result, that I got a slightly stale result (e.g. it was updated within whatever amount of lying about the height I'd fail to detect), or that my attacker has a serious amount of computing power being employed to give me a stale result about a name.
I don't quite see what the problem is. If you don't trust a peer to deliver accurate data, just make sure that you ask lots of peers and that you exclude the outliers. It's already true that the client has to trust that it will get a complete, accurate, and up-to-date complete block chain from its peers.
If you have the block headers (which are quite small), then your trust is limited to that your peers aren't lying to you about the block height and aren't telling you only about some fork. But you can trust that such a fork would not be very long due to the extreme computational cost, and that the block height could not be too outrageously wrong because you know the current time.
The fact that peers can DOS attack you by denying you information can't be avoided but it's also detectable and once detected you can try to seek more peers or at least refuse to do anything stupid.
I 100% believe that eventually end users will not be downloading the whole block chain as they do now and will have to utilize service providers that can answer queries about the block chain (themselves keeping the entire block chain); I already wrote up a proposal for this on this forum. I'm even working on my own bitcoin client that will have support for this. And I believe that the only way for it to work is for the protocol to be 'open' so that anybody can implement it, because for the reasons that the O.P. brings up and that I point out in this response, a peer just cannot trust a single other peer to provide accurate information and has to have the ability to discover and talk to many peers for the safety and security of redundancy.
Asking multiple peers is a good and fine thing, but it has _serious_ limitations. Attackers can often control your network connectivity, so they can simply make themselves all your peers an you have no way to detect this. Even without network control a sibyl attack can be quite effective: by running thousands of fake peers on a few hundred networks (e.g. just by having simple proxies on those networks) you will very likely end up as all the peers of quite a few nodes. Querying many also results in N-fold increases in network load.
If a client can use the blockchain proof of work to prove most of their required data, then it only needs to consult multiple peers to obtain confidence about the true identity of the highest block, and attacks performed against this clients are limited to attacks about the content of very recent blocks.