Hi, I read some of the posts and I try to summarize it for later readers, and please correct me if I say something wrong:
1. There could be a problem if  out of some reasons there aren't enough people relaying transactions. Example: Bitcoin gets to Visa proportions and only miners have the hardware requirements to receive/relaying transactions. They will (of course) not relay transactions if there is no incentive.

Solutions:
1) Pay all (or statistically some) node that relayed transactions somehow
2) Punish the (greedy) nodes, by cutting connections to them. Then a miner not relaying transactions will receive much less transactions (he could include in his own block)


My Comment:
I think that it it very important to think about it. The solution 2) wouldn't require a change of protocol (I think) and is a quick and easy way to get everyone to relay transactions (even if the network is just composed of miners (due to hardware requirements)).

1) would certainly open a whole lot of new set of problems/attacs, but If REALLY carefully thought through would solve the problem more elegantly than 2).

An other point to 2): Instead of counting how many transactions a node relays (to determine if they are greedy), maybe it should count how much transactions fees they are relaying (just an idea...  but I don't know if that is better or worse, than counting the number)


Ok. It's good that we think about it, thanks to the guys from MS (yes I run Linux)!