A lot of it is caused by the fact that, unlike the rest of your body, your feet and toes don't actually move that much when you are cycling so it is quite common to lose circulation to your feet while your other muscles are working hard. Also your feet get quite a lot of wind exposure while you are cycling.
I have Raynauds in my toes, it's not particularly painful, just annoying feeling some of my toes go numb and then having to wait an hour or more for them to 'thaw out'. And once I start to feel my toes going numb there is no going back until I get somewhere warm and take my shoes off. It effects me wearing all sorts of shoes and socks, and isn't that dependent on how cold it is. I've had it happen when walking in normal shoes when it is 4/5 degrees, and been perfectly fine when walking in ski boots at -10 degrees.
A lot of it has to do with the fit of your shoes and socks I think. What I have found is that it is sometimes caused by over tightening the shoe on the very top of my foot. When you do things like cycling or skiing/snowboarding this tends to put a lot of pressure on the top of your foot and can cut circulation. It's frustrating though, as for cycling and skiing/snowboarding it is preferable to have as snug a fit as possible.
Other things that help me include wearing one pair of thick socks rather than multiple pairs of thin socks.
Also, if you've been cycling in the rain, make sure that your shoes are completely dried out before the next time you go out. Damp shoes/socks make it much worse in my experience.
I think those overshoes might be a good idea, the windchill can be quite a big factor.