Just so it's clear what I'm responding to...
Interestingly, it looks like there is actually a way of making coins immune from this particular attack that doesn't require any kind of trusted central authorities and can't be used to fork the blockchain. Unfortunately it'd be a huge pain to implement correctly and wouldn't be able to deal with 51% double-spending attacks.
The trick is that there's no inherent reason why the Bitcoin blockchain actually had to be in the form of a chain. Simply add a rule that blocks can merge multiple non-conflicting forks of the blockchain by having multiple parents, calculating its total work as the sum of its work and work done for all its ancestor blocks. That way, it doesn't matter that Eligius is mining faster than the rest of the network because we can use the attacker's work against him - our non-attack versions of the best chain are counted as having the strength of all his work plus all ours, and the only way he can benefit from this effect is if he includes other's blocks and transactions which is what we wanted in the first place!
There's almost certainly some subtle flaw in this and it'd be a nightmare to implement correctly and in a way that couldn't be exploited, but on paper it seems like a clever idea. Don't think I'm going to go through with it though. (There are a whole bunch of subtle details that have to be taken care of. For example, we need to cap how far back a fork that's being merged can come from to block spam, but this limits the power of this scheme against denial-of-service.)
Dear God. You may have just solved the latency problem. By the latency problem, I'm talking about the fact that an attacker can generate blocks on a low-latency network without orphans, whereas the main network is more likely to have orphans. If this problem is solved, there would no longer be as much risk in lowering the target block generation time to a few seconds. Think about the implications of that for a second. The Finney attack would become almost useless, since you could no longer hold onto a pre-generated block while you spend coins elsewhere. A smart person would still wait for 60 minutes worth of confirmations, but it would definitely reduce the risk of accepting transactions quickly.
Here's a quick spec. Interestingly enough, it would be possible to merge it with Bitcoin as a recommendation for clients by replacing certain MUSTs with SHOULDs. However, it would be most effective on alt-chains.
Definitions:
VALID - means that the orphan would have passed all block/transaction validation checks at the point where it would have ended up in the chain. The orphan MUST be from a chain that, when you add the orphan, has a lower total proof-of-work than the current chain. Additionally, to prevent an attacker from using this against the main chain, the transactions in the orphan chain (ignoring coinbases, which are discarded) MUST NOT conflict with the current chain.
To start, this spec only affects a blockchain's total proof-of-work. All other blockchain rules remain in effect.
Assumption: all VALID orphans would have increased the total proof-of-work of the main chain if the network had zero latency.
A block would be redefined to allow additional parents. However, there will still be a main parent, just like today. In Bitcoin, this could be added to the coinbase instead of making a new field in the header. (I wonder if the merged-mining format could help here...)
When a mining client receives a VALID, unused orphan block/blockchain that connects to the main chain somewhere in the last X blocks (where X is a number that I haven't really decided on), they SHOULD add that orphan as an additional parent to the current block they are working on. Additionally, they MUST(/SHOULD) add all transactions that haven't been confirmed yet to the current block.
When a client receives a block with an additional parent, it checks that the additional parent is VALID and connects to the main chain somewhere in the last X blocks. If the additional parent doesn't connect directly to the main chain, the client MUST recursively lookup that orphan's main parent until it finds a block that has either already been merged with the current chain or was part of the current chain. From there, the orphan chain's proof-of-work is added to the current chain. Any additional parents included in the orphan chain are then also processed in the same manner.
This is most definitely more complicated than it's worth for Bitcoin, but it might be useful for an alt-chain. The only attack I can think of off the top of my head to reduce the effectiveness of this is to send different double-spend transactions to each peer, in the hopes of making any orphans that are created unmergeable. However, this can be reduced if the miners actually choose to communicate with each other and decide which transaction to go with, or use other such heuristics.
Also, there's a neat side-effect if you require a merge to also include the unconfirmed transactions from the merged chain: an attacker making empty blocks, and thus refusing to do a merge, would be beaten every time a real block is released by an ever-increasing amount of work.
Example: (number indicates total proof-of-work)
Attacker: 1----2----3----4----5
/ \ \ \ \ \
Main: 0 2----4----6----8----10