Sally and I EACH flip a fair coin. We then each guess what the other person got: I guess what side Sally's coin landed on, and Sally guesses what side my coin landed on. We win as long as at least one of us is correct.
I understand that to ensure that we win every single time (regardless of actual coin toss results), I should guess that Sally got the same result as me, and Sally should guess that we got different results. This is because the set of results {HH, HT, TH, TT} is such that we both either get the same result or different results. 
However, say Sally forgets the strategy, and she guesses at random (1/2 chance she guesses that I got heads; 1/2 chance she guesses that I got tails). If I don't change my strategy (and keep on guessing that Sally and I got the same result), then we only win 75% of the time. My question is as follows: how can I re-strategize such that we win more often (given that Sally guesses randomly)? 

You can't do better than $75\%$ because Sally's guess is now independent of all other events, and you can't change that by anything you do on your own. No matter what strategy you pursue, you have a $50\%$ chance of guessing Sally's coin correctly. The original strategy was able to do better than $75\%$ because Sally's guess was dependent on her coin. Now that it isn't, Sally has an independent $50\%$ chance of guessing your coin. By independence, the probability that both guesses are wrong is $25\%$. Perhaps you can take comfort in the fact that you also can't do worse than $75\%$ with any strategy.
