I am really interested to see use cases where these micropayments work in the other direction... Considering that micro-payments start with a contract between two parties (a service and a client), a service providing distributed computation could in effect pay a commission to clients that contribute processing power.

In this way the computation doesn't need to be aligned to a particular hashing algorithm or specific hardware. The computation likely isn't time sensitive so anyone could participate, and their effort wouldn't be wasted. Pricing could vary, but could be as simple as 1 satoshi per Hz per second...

It doesn't even need new infrastructure to implement. WorldCommunityGrid.org could release an updated client that sets up a Bitcoin address for payment, provides you with the private key, and on their server they run BitcoinJ to facilitate the micropayments.

Any other novel use cases where services pay clients using micropayments?