LM7805 Voltage Regulator stops working when input voltage increases
This is almost certainly because of thermal shut-down. These kind of old linear regulators perform poorly when they have to go from such relatively high voltages down to 5V - there will be lots of heat no matter the load connected to it.

When thermal shut-down occurs, the output voltage from the IC drops just as you describe. Then when the part cools off, it goes back up again. This leads to oscillation. 

You will absolutely need a heat sink, and you could fiddle around with various heat sinks in an attempt to stall the thermal shut down to higher input voltage levels. A less expensive and less problematic solution is to use a LM317 first, to take the voltage down to 15V or so, then place a 7805 "in series" after that. 

This is how it was done "back in the days" when these parts were new and it is still ok for hobbyist solutions (or if you actually need heating to drive out moisture), but it isn't how professional designs are done any longer. You should strongly consider using a switching buck regulator instead.

Also, I don't understand your relay circuit. It says 5V relay, yet you feed it the 27V-something voltage. I'm not sure what those 4 resistors in parallel are supposed to do, current limiter? Looks very fishy, did you think they form a voltage divider somehow? You will need a 24VDC coil relay, and even then that coil won't be happy if you stray too far from the nominal voltage.