If I were to guess, we may have had a hidden clue to this mystery in the episode "Who Watches the Watchers" when we see a planet full of "Proto Vulcans" who curiously had a similar kind of ridges that the Romulans were given. My take on that, is, that the Romulans may have been a parallel offshoot of the Vulcan race that can trace a common evolutionary lineage. Much like if modern humans still shared space on Earth with cousins Homo Erectus or Homo Habilis. Perhaps that other species was persecuted to the point of rebellion and secession during Vulcan's warlike period that Spock mentioned and Enterprise expanded upon.
We saw an ironically similar interaction between Romulans and Remans in Nemesis, the latter being completely subservient to the former until Shinzon's rebellion began. One wonders if they also somehow share some odd lineage commonalities as well, or may have been the original inhabitants of that star system that were subjugated by the Romulans when they arrived. In any case, Romulans may be simply a branch of the Vulcans greater genetic tree (as opposed to some aggressive political faction of the same evolutionary strain, like most believed). They've been a space-faring race for much longer than most of the other regional powers. I'm honestly surprised we haven't seen more lost Vulcan colonies.
The question is, why did THEY change their appearance between TOS (movies) and TNG? Ambassador Caitlin Dar in TFF had a smooth head (but she was admittedly half-human in the original script and novelization) as did Ambassador Nonclus in TUC. Something happened after that time. The Klingon problem has been explained, albeit ham-handedly. The Romulans' appearance, while not as pronounced a problem, still raises questions.
Another thing to take into account is "Reunification", where Spock appeared to walk freely amongst the Romulans in their streets and cities, without being "outed" as a Vulcan, so clearly there are still a lot of smooth-headed Romulans around as to not make his presence an oddity. Just don't see them as much for some reason.