How to recover from a double spending attack?
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.