Video compression using low power processor
I suggest you look at BTC compression. A main advantage is that, once you set your parameters, you can calculate reasonable accurate how much CPU power it takes. 

You still have to process 640x480x25 = 7.68 Mega pixels/sec. Thus a 64 MHZ MCU is unlikely to be able to do the job as that gives you only ~8 clock cycles per pixel. On top of that you need clock cycles to read it in and write it out. I think you need a 600 MHz ARM if you have no other hardware to support your video processing.

Then you want to 'record' the stream. Where to? You can write it to and SD card but that also uses up a good number of clock cycles.  

"I feel I'm missing something quite obvious for everyone except me in this world for such a typical application." It may be typical but that does not mean it is easy. 

Maybe just buy a Raspberry-Pi with camera....