@mpoly, it sounds to me that either your power supply output voltage is too close to the 22.5V threshold you have set in your M911 command; or you have a bad connection between the PSU and the Duet; or the 250W power supply rating is marginal for your machine. So here are some thing to check:
Temporarily reduce the power fail threshold (S parameter) to a lower value, e.g. 20V (S20 instead of S22.5). Then run a CNC job. Then run M122 and see what minimum and maximum recorded voltages it reports. Note, running M122 resets the minimum/maximum recorded voltages after reporting them, so only the first M122 report after running a job gives useful values.
Check that the VIN terminal block screws on the Duet are tight.
Are you powering anything from the 250W PSU apart from the Duet (and hence the stepper motors)? As a CNC machine doesn't have heaters, I think a 250W PSU should be adequate unless you are powering additional devices from it, such as a spindle motor.
HTH David