I don't think there are any easy answers to this one (or if someone has one, I've missed it).
If your application requires regular full reindexing, as ours does, your options are limited. What we're playing with right now is a multicore Solr setup with one live core being used by the live application, while we fully reindex the second (offline) core. Then we simply switch which core the live application points to. Voila, full reindex with no downtime on search.
Or at least, that's our hope. This isn't in production yet so I don't know if we've found all the possible gotchas.