it wouldn't have to be a SPoF, you'd just replicate your server and add an additional record, if the client can't reach the first server it failovers (failsover? fails over?) to the next one.
I don't think it adds to the complexity too much and it's hardly going to be slow - it'd be much faster than the time it takes to send even the smallest email message.