TIP120 Transistor + Solenoid Failing Randomly

I don't see any decoupling capacitors on your ICs on the veroboard. PSU noise could be causing false outputs from your logic. Try putting 100nF capacitors from ground supply pin to power supply pin on each IC. Keep the leads as short as possible, put them on the copper side of the board if this helps you to meet this objective.

Without these capacitors the supply voltage at the IC pins can drop to a level where the behaviour of the ICs is non deterministic over very short timescales. The faster the logic family the worse the problem gets.

Thermal Resistance, Junction−to−Ambient Rja = 62.5°C/W , Pd = 0.5A * 0.8V = 400mW = 25'C rise , looks ok.

Although you may have grounds tied together externally, they should be also done on board.

If you switch solenoids simultaneously, you may have significant ground shift and exceed the spec for Emitter-Base Voltage VEB = 5.0Vdc ( reverse spikes). So joining grounds on the board and adding low ESR decoupling e-caps will help the snubber diodes from raising the ground voltage between 12V return and 5V return which drives the base-emitter.

Not having a good ground plane and decoupling caps and possibly switching off more than 1 solenoid at a time would explain random failures.