The valves are grounded. They would not work if they had no ground connection. Your diagram shows that they are grounded. But they are grounded to the 30V circuit ground.
If the 5V and 30V supplies had a common ground, and there were no flyback diodes for the solenoids, then the reverse voltage/current from the solenoids could reach the Arduino through that common ground and cause resets or even damage the Arduino. But there is no common ground, and it is not needed. Therefore that may not be the reason why the arduino is resetting. There may be some other reason, perhaps radio interference or induction between unconnected cables.
Capacitors across the solenoid terminals (in parallel with the flyback diodes) may help to suppress radio interference. 0.1uF ceramic or polystyrene caps, rated for at least 30V, could be suitable.
No, I would not advise that. 1N4148 is a small signal diode, not meant for heavy duties like this. 1N4148 can run at higher frequencies than 1N000X, but both diodes can run at much, much higher frequencies than any relay.
Your 30V PSU and your 5V PSU both have grounds. But they are separate. If you connected the ground from the 30V PSU to the ground of the 5V PSU, that would be a common ground. But you don't want or need to to that in your circuit.