How to prevent a microcontroller to reboot due to Vcc fluctuations?
I agree with Lucky Bot that PSU "holdover" is not a problem here, and I agree with Spehro Pefhany and Lucky Bot that this looks like an EMC problem. 

What happens when the pressure switch switches off is that an inductive load gets abruptly turned off. The "magnetic inertia" of the inductance tries to keep the current flowing, but you've barred the path by a very high resistance... which results in an immediate mighty voltage spike across the inductor's terminals, typically pulling an arc across the mechanical switch contacts, excited by the motor's winding. The arc itself is noisy, and the switch can be bouncey. Apart from the voltage spike, the brief but mighty dI/dT also produces an EM pulse spreading through the "ether" from the inductor(s), possibly inducing some glitches/noise in the various PCB traces around your Arduino.

There's a similar problem with relay coils, e.g. driven by a transistor. As the transistor goes open circuit, its collector suffers a spike from the relay coil - which is why the transie should always be protected by an anti-parallel "flyback diode".

Properly blocking the power rail to your Arduino MCU is one partial countermeasure. Unfortunately, attention to PCB layout is another one. At the motor, you can try inserting an EMC filter in the power wiring, and/or pull a ferrite bead/ring/sleeve over the wires, or some such.

Do you have a 'scope to maybe look at some interesting points around the MCU? Such as, the PSU input and the reset input? 

That said, digital circuitry can be tough to debug upon this symptom, even with a 'scope at hand. Your advantage is that the Arduino is a simple board, and well documented. I haven't studied the PCB myself. Generally, in computers, the reset line is not a single trace going from some switch or header to the MCU, it can be a more complex network in itself, with several "sources" of the reset signal. A good place (starting point) to look for reset glitches is at the CPU's RESET input pin. And, you may face an interesting uncertainty: the glitches that you see on a 'scope, do they come from the trace or "node" that you're watching, or are they possibly induced into the "loop" between your probe tip and the probe's ground leash? For comparison, try shorting your probe tip to the probe's ground clamp, and generate the EM spike, to be half sure what you're looking at.

You may find that the amplitude of the EM pulse / spike is somewhat random, or very random. Apart from other misc random influences (such as the precise unique one-time pattern of the "bounce" of a mechanical relay contact) the sinusoidal shape of the current through the motor can also be a factor in AC-driven inductive loads. What's random here is the instant in time vs. the instantaneous phase of the sinewave, where the relay contacts open. Some solid-state switches (transistor-based, i.e. PhotoMOS or IGBT) can cause EMI too, by the same mechanism. They don't exhibit mechanical "bouncing", but the abrupt turn-off (dI/dt) is still there. Solid-state switches based on a triac or thyristor should be more polite: they switch off during a zero transition. That's why they only work for AC.

As for some references... speaking of blocking power to IC's by capacitors, try reading through this topic and follow the links to the Kemet KSIM and to the Murata C39E appnote. Those two sources dissect the "choice of blocking capacitors" in meticulous detail :-) And, maybe take a look at this video on spiking caused by inductive loads on turn-off (and the purpose of flyback diodes, though a flyback diode will only protect the switching transistor, and will not prevent the EM pulse spreading though the ether). You seem to be into DIY... ferrite sleeves for power filtering can be found in scrap PC power supplies or various cords and even data interconnect cables. A proper power line filter for your motor (LC PI or whatever) can easily cost more than the Arduino, but may be worth the investment. 

If you try some ferrite sleeves or rings, you can put several in series, or wind a couple turns around one, you can make a common mode choke by inserting or winding the live and return alongside each other through a shared ring... And whether you try ferrite sleeves/rings or an LC filter (or both), it may make a difference if you put the filter close to the motor vs. close to the switch. I'd say close to the motor would be better, as it would make the "parasitic antenna" shorter for the radiated RF energy... then again my view may be naive.