Overshoes
When the boots' warmth is not enough, you can use overshoes.
Basically, it's nothing more than a sack made of cloth , which you put over your boot and fasten somehow:

This helps you in two ways:
- It creates an air pocket around your boot, reducing heat loss.
- The snow now melts not on your boot, but on the overshoe, drastically increasing the time before your shoe gets wet (and cold).
You can try to shop for something like this, but you can easily create it yourself as in the picture above: fold a cloth to make a sack, sew 3 sides of 4, add some laces and that's all. You can use any synthetic (and maybe waterproof) cloth like Oxford or Cordura.
If your sewing skills are higher, you might end up with something more attractive and better shaped:

(some other designs are shown here)
If you need to use it with SNS/NNN ski boots, make small cuts on the toe. (The other option for skiing may be removing overshoes sole and glueing the remainder to the boot - a lot of expensive ski boots are made like this, but you can add another layer;)).
Durability upgrade
As you may have noticed, this design implies a relatively thin fabric being between your sole and the ground, so if you are not wearing skis or crampons, it's damaged easily. So it's recommended to make the sole of the overshoe thicker. The best thing for walking is an overshoe combined with rubbers/galoshes:

Why, you can sacrifice some huge-size rubber boots for this.
Warmth upgrade
Overshoes by themselves provide additional warmth, but this may be not enough. To get really warm one should add another layer - warm overshoe ("chuni") - between the boot and the overshoe. Basically it's crafted just alike, but you use a warm cloth (e.g. Polartec-100/200) and you don't need laces.

P.s. And yes, this works just fine at -30°C ;)