I think Gavin has alluded to possibly rewarding those who run full nodes, which I think is the way to go. I don't see any reason why miners should get rewarded, yet those who run full nodes and eat the bandwidth/disk space get nothing.
When running a node becomes expensive enough that people can't do it for free you'll still be able to find full nodes willing to accept incoming connections. You'll pay for that service in a variety of ways:
1) Transaction fees: You connect directly to a miner who lets you do so because they want your transaction fees. They may require some # of transactions per unit time, and part of the agreement may be that you only send transactions to them. (easily verified) In return they'll run your bloom filter against incoming blocks, although don't be surprised if they force you to give them a bloom filter specific enough to identify exactly what addresses are in your wallet as part of the deal.
2) Pay-for-service: You pay for the service directly. In return they resend your transactions to miners to get them mined, possibly with preferential deals (kickbacks) that may or may not be public knowledge. They also run your bloom filter against the blockchain, and again, they may or may let you do so in a non-specific manner. Given AML regulations I wouldn't be surprised if the services that operate out in the open only allow you to tell them what addresses you are interested rather than a bloom filter obscuring that information. (AML rules apply to case #1 too)
3) Datamining: Google and other search engines already provide a lot of services purely in return for the data they can gather. The blockchain itself is a rich source of transaction data, made richer by figuring out the real identities behind the pseudonymous addresses on it. Just like #1 and #2 if you can determine who is sending what transactions and owns what addresses you can integrate that into a rich dataset to do things like get real-world information on what vendors are actually popular, which in turn can feed search engine results and other services.
It'll be interesting to see how AML regulations apply to all these services in the future. I suspect they'll eventually be subject to the same know-your-customer rules as any other financial service provider to help authorities link identities to Bitcoin addresses. This doesn't have to be very intrusive: in case #3 that might be as simple as using your Google login to authenticate with Google's Bitcoin servers.