Power HC-SR04 from microcontroller pin and MOSFET
After much experimenting, it looks like it all came down to the breadboard connections not being strong enough. When I try to "push" the MOSFET and wires connected to it in a way that forces them to touch, it seems to be much more consistent; when I manage to get a good connection and don't move the board, the distance is very stable. I also added a capacitor between +5V and Gnd for the HC-SR04, to absorb any inconsistency in the signal given by the pin of the PIC and the MOSFET. I will soon solder everything on a prototype board and will be able to confirm that this was the issue.

The wake up time of the HC-SR04 seems to be about 60ms. The minimum suggested time between 2 measures to avoid collisions from a previous signal is about 60 ms, so I tried to wait 60 ms after powering the sensor also. Waiting less that that does give some incorrect values, so I would recommend keeping a delay of 60 ms or more every time you power the sensor back up, as well as between every measure.

I guess the solution is simply that the HC-SR04 needs to be powered by a stable signal, which was not the case on my breadboard.
Anyway, thanks a lot for the help!