My bet is on boot0; Check that you've got it pulled low.
The boot0 pin selects where the MCU will start executing code from when it boots up, ie. comes out of reset. If boot0 is low, it'll execute your code from flash, but if it's high, it'll execute the internal bootloader from the system memory.
My guess is that you have left boot0 floating, and when you're doing a cold boot (ie. disconnecting and reconnecting power), it'll be close to zero, so the MCU will boot your code from flash, but when you do a warm boot with the reset signal, the pin will have floated to a higher value, is read as high, and the MCU will boot to the internal bootloader from system memory instead of your code.
This explanation assumes you haven't touched the boot-related option bytes, which would change the behaviour. Also, in case you'll be working with different STM32 MCUs at some point, please note that they can have slightly different behaviour. Some have different boot-related option bytes. All I've seen so far have had a boot0 pin which behaves identically, but some also have a boot1 pin (which might be shared with a gpio pin) that you might also have to set correctly. In the MCUs I remember seeing, though, boot1 is only relevant if you want to be able to boot from system memory or SRAM.
This strongly smells of the solenoid return currents and inductive kickback paths not being handled properly. There are large and fast voltage spikes at the solenoids. Sometimes one of these couples enough to the microcontroller to confuse its internal logic. The reset mechanism is being tripped, but not by the external MCLR pin.
Absolutely the first thing you must do is ADD A BYPASS CAP across the micro's power and ground pins! Put a 1 µF ceramic cap physically as close as possible between the power and ground pins. This is exactly the kind of symptom a lack of bypass cap would cause.
Other than that, there are two remaining obvious suspects: poorly designed power and return current paths, and poorly handled inductive kickbacks.
Your schematic doesn't give us any idea of the physical layout of the power and return currents to the solenoids. The current loop of power supply to solenoid and back to power supply should have as little in common as possible with the microcontroller power loop. For example, if the two share a significant section of a ground wire, then the high solenoid currents in that ground wire could cause a ground bounce for the micro.
Ideally, there are separate power and ground feeds to the solenoids and the digital circuitry, with these connected at only one place close to the power supply. Then of course there needs to be proper bypassing of the power at each point of use on the digital side.
You do have a diode that is supposed to catch the inductive kickback, but you haven't shown any specs. No, a 1N400x is not appropriate here. I'd rather see a Schottky diode, due to their very fast response times.
Placement of the diode is also important. It is good to have some protection at your driver circuit in case stuff happens, but to really deal with inductive kickback it should be shunted as close to the source as possible. You want to contain the nasty current in as small and local a loop as possible. Small minimizes its radiation and capacitive coupling to elsewhere. Local keeps it from causing ground bounces and the like to other parts of the circuit.
As a experiment, try adding Schottky diodes in reverse across each solenoid right at the solenoid. Perhaps you can't put them there in final production, but do the experiment anyway to see if things change.
I suspect by observing proper hygiene, things will work a lot better. After you fix this mess, reflect on all the times you were told to use bypass caps, carefully place return current paths, keep the loops small, etc, and you thought "bypass schmypass, blah, blah". Now you know why it matters. Yes, you can get away without this sometimes, but sooner or later it will catch up with you. It just did.
Best Answer
I've used these in various similar situations, and perhaps one of the would suit your application:
Although an ATTiny seems like overkill, it's sometimes convenient: they are pretty small (6-pin, 8-pin) and $0.25/unit!
It's worth noting that many MCUs (including ATTiny) have brown-out detectors, which are specifically for this kind of application.
At least ATmega328 and ATTiny25 (and I'm sure many others) work like this:
(image and quote from Atmel datasheets)
Many other MPUs' brown-out detectors will have very similar properties, though of course the details will vary.