The question whether two-variable logic with two linear orders is decidable for general (not necessarily finite) structures has been left open in [1]}, [2]}, and is settled here affirmatively. Beyond settling the question itself, we believe that the techniques developed here might also be interesting in their own rights and applied to other problems, much like in the case of finite satisfiability, where the used techniques were later exploited in work by Dartois, Filiot, and Lhote on transducers [3]} and in recent work by Lutz, Jung, and Zeume in relation to description logics [4]}.
