But they _do_ get to communicate beforehand and could collude to always vote the value of the coin they tossed as their guess for the other coin toss?

Isn't that step 1 where they can agree on a strategy (of which randomly, independently guessing is just one possible strategy)?

Are you the author of the original problem? Perhaps the English prose could be tighter to be more correct with the solution you have in mind.