I'm not so sure about this much but, I think they're hail from Europe.
It's never said, although most signs point to France. Flandre is another term for Flanders, a region in France, and Voile is apparently a French word meaning "veil;" alternately, it could be a play on "voila!" - as in, what a magician says when doing a trick - and, again, this is apparently a French term. Remilia sounds kinda like a French name to me (or at least a "romance language" name, as opposed to an English or Germanic name), and the Scarlet Devil Mansion has a sort of French architecture to it; it looks a bit like Versailles. And, according to ZUN, Meiling's boss theme is "composed with the image of the French settlement in Shanghai in mind."
So yeah, I'm thinking France.
Well Remilia's stage theme is "The Young Descendant of Tepes". So it would be logical if Remilia was a descendant of Vlad III The Impaler (Vlad Tepes). He was prince of Wallachia, part of today's Hungary. So it would be logical if it was Hungary i think.
Remi saying that she's decended from Vlad Tepes is a lie she spreads. ZUN repeatedly said that they're no relation.
However, if it turned out that the Scarlets weren't French (or Belgian), that region of central Europe - Austria, Hungary, or Romania - would be my next guess.
I don't think Remilia come from Romania or something like this. Her name, "Scarlet", definitly sound english. It may be a nickname, but Patchouli is definitly english, and I don't think she travelled a lot before comeing in the SDM to live.