While I haven't managed to beat @Jaap's result I think I gained some good intuition on the problem that is worth while sharing:
The centre piece of the advanced strategies we have seen is the following neat little trick:
Assume for the sake of argument that the events each player can see form a fixed recurrent sequence and only the phase is random....
In this paper about Levine's hat puzzle there is a better strategy with a winning probability of $0.7$.
Let $a_i$ be the coin toss outcomes that are told to $A$, and $b_i$ the ones that are given to $B$. This is a bit easier than having the tosses interleaved as a single sequence.
The strategy is as follows:
Now let's calculate the probability of winning.