How to recover from a double spending attack? I found myself incapable of answering what would happen in this case, so here it is:


A hacker (Mr Hacker) spends UTXO_1 and UTXO_2 in TX_1, depositing the monetary value of all TX_1's outputs into a Service (eg a payment processor).
A legitimate user (Mr Legit) spends UTXO_3 in TX_2. Again, TX_2's outputs targets the same Service 
Both TX_1 and TX_2 make it into the same block and get one confirmation by the network.
The Service immediately spends UTXO_1 and UTXO_3 in TX_3 to pay Mr Legit and UTXO_2 in TX_4 to pay Mr Smith.
Mr Hacker then decides to double-spend TX_1 and for that reason he creates TX_5 which "redirects" all outputs to himself. Mr Hacker is a miner so he is able to perform all the hashing work to make the double-spend successful. He is also lucky and the double-spend succeeds.


So the question is:


Have all TXs before TX_5 (TXs: 1,2,3,4) been invalidated or just TX_1, TX_3and TX_4 (TX_3 and TX_4 spent an output previous controlled by TX_1 which was double-spent)?
Mr Legit could see 1 confirmation for TX_2 before the double-spending. What does he see now? What does Mr Smith see in his wallet, before and after the double-spending?
The Service realizes that a double-spending took place and needs to recover from that broken state. What does it have to do to get back to normal operation? Does it have to re-send all the TXs? Does it still have in place the deposits made by TX_2 after the double-spending or does it have to do something to re-claim these outputs?
How can the Service prevent Mr Hacker, who also has plenty of money to spend, from repeating the same process forever just to ruin the Service's smooth operation, rather than (the Service) waiting for more confirmations before sending out the payments?
I had to diagram this out as the transactions and block chain might actually appear:

    Inputs/Prev Outpoints    Outpoints
TX1 A:0                      TX1:0, TX1:1
TX2 B:0                      TX2:0
TX3 TX1:0, TX2:0             ?
TX4 TX1:1                    ?
TX5 A:0                      TX5:0


                (TX5)
Block A ------&gt; Block C ----&gt; Block D
         \
          ----&gt; Block B
                (TX1, TX2)


To answer your questions:


TX3 and TX4 are not valid in any block chain which does not previously include TX1.  TX1 can't be included if TX5 is already a part of that chain because TX1 and TX5 both spend outpoint A:0.
TX2 is never invalid, so it If the wallet sending TX2 downloaded the now-stale block, it would've shown 1 confirmation. After the wallet switched to the new best block chain, it would show 0 confirmations again because neither block C nor block D includes it. After another block on the best block chain does include it, it'll return to 1 confirmation and increase from there.
If the service still wants to make the same payments, it has to create new transactions (TX6, TX7) using inputs that are still valid (e.g. TX2:0). If it attempts to resend TX3 or TX4, other nodes may ban it for attempting to relay invalid transactions.
To prevent future fork-based double spend attacks, the service either has to wait for more confirmations or find some non-Bitcoin way to collect money from double spenders, such as requiring registration with state-issued identification.  I know requiring more confirmations requires waiting more time, which is inconvenient, but it's the only decentralized method we have for reducing fraud risk.