The notion of their creation is absurd to refute, because they travel through time. The ruins on Venus could have been made tomorrow by the Vex traveling to our yesterday...so in our timeline, they'd always have existed. So the notion that the Vex were created on Mars isn't outside the realm of possibility. They could have been created on Mars, millions of years in the future, then went back in time and set themselves up in our past.