Let say I put a 10M resistor, that is rated voltage of 250V, on a 1KV rail, something will go wrong for sure.
Actually, "for sure" is unlikely -- they aren't going to break down at exactly the rating. But you have no idea where they actually will, and the manufacturer provides this rating as a "it's pretty unlikely to break at this voltage", given the range of environment it's expected to be in (presumably, a certain amount of solder flux, humidity, dust, etc.). (I don't know if they're actually certified to tolerate some combination of this, I'm just guessing.)
That said, it's worthwhile to use several more than the required (minimum) rating: it's very likely that, if one fails, it will fail more or less shorted, and increase the stress on others by as much. So with 4 being rated minimum, 5 is not a bad idea, but I might even go with 6 or 8. Or 9 or 10 just because the value will come out better (e.g., 9 x 1M into a 1M resistor, for a 10:1 voltage sense divider).
Amazingly enough, there are small (0603 to 1206 sized) chip resistors rated for extreme voltages, like 10kV (at least in peak). The "gotcha" is, they have to be potted to reach that, as you might expect given the size of the parts!
I would recommend 1-2W through-hole resistors, maybe 3-4 in series (however many are needed for the rating, using the above method), though I don't think there's anything wrong with using a larger number of chip resistors in series.
By the way, if you're using this for AC measurement as well, even just for low frequencies, it may be necessary to add capacitors across the resistors. Try to use one capacitor in parallel with each resistor. This keeps the voltage equalized along the chain, and compensates for capacitance to ground (which varies along the chain, and makes weird dips in the frequency response). You also need a capacitor across the 'bottom' resistor, and in a large ratio divider (like 100:1 or more), it needs to be quite large in comparison, and preferably, adjustable.
Tim