I think you are making it more complicated then it needs to be. You basically have two choices..
If you Unity Primary and Failover pointed to (1) Exchange store and exchange goes offline, Unity will still work. It spools the voicemails, takes messages and waits for Exchange to come back online, then dumps the messages over.
The other way you are thinking of... you would need to put Exchange into a Cluster. This will help Unity point to one store, but spread across a cluster. If Exchange01 goes down in a 3 server, Unity does not care, because it still sees the store being up.
Make sense?