> Some PC somewhere with storage is a bigger problem

Both an embedded microcontroller and a PC have storage. The reason you can power-cycle a microcontroller at will is because that storage is read-only and only a specific portion dedicated to state is writable (and the device can be reset if that ever gets corrupted).

Use a buildroot/yocto image on the PC with read-only partitions and a separate state partition that the system can rebuild on boot if it gets corrupted and you'll have something that can be power-cycled with no issues. Network hardware is internally often Linux-based and manages to do fine for exactly this reason.