Ideally invalidation happens on an offline queue with retry support. Server down? Reschedule job and retry later.

We use Delayed Job at Posterous for things like this. Resque works too.