Even on Earth, we have millions of different, unique cultures. The intractability of the Muslim and Christian worlds alone makes each alien to each other.
Hardly. There's no "intractability" there. Islam and Christianity are both offshoots of the same Abrahamian religious tradition, along with Judaism. They have far more in common than they have with, say, Hinduism or Buddhism. Indeed, the Qu'ran explicitly defines Christians and Jews as fellow People of the Book and commands tolerance toward them -- so Muslims who treat Christians and Jews with hatred are betraying the tenets of their own faith. In the current generation, there are factions prominent in the Islamic world who are hostile toward outside cultures, but that's historically a fairly recent development; prior to the mid-20th century, Jews were actually treated much better in the Muslim world than they were in Christian Europe.
So not only do we have many different cultures on this one planet, but those cultures can change drastically over the course of a single century. If anything, this is one thing I think Enterprise got right, portraying a 22nd-century Vulcan culture that was very different from the Vulcan culture we saw in subsequent centuries.
Time frames don't match up. Someone would have noticed if a bunch of Americans and Chinese went missing in the 1960s.Couldn't the Omegans also be the result of the Preservers efforts?
Indeed. Also, there were individual Kohms who were over a thousand years old, and that the war that devastated Omega IV happened over 10,000 years in the past. The Preservers would've had to take them back through time, and there's no evident reason why they would've done that.