PIC16F18855 runs at half the clock frequency when I turn it off and on too quickly
This is not an explanation for why it was happening, but I found a fix.
First thing I tried was setting the fuse bits for RSTOSC_EXT (i.e. #pragma fuses HS, RSTOSC_EXT) on the basis of what Spehro said in the comments, but that didn't work for me. What I did was add in the following (note that OSCCON2 is the actual setting, and OSCCON1 is the buffer):

if(OSCCON2 == 0x60){
    OSCCON1 = 0x60;
    OSCCON1 = 0x70;
}


My reason for trying this is: OSCCON2 is the actual setting, and will load the value in OSCCON1 when its ready. From my earlier investigation, I knew that the correct value was in OSCCON1, and OSCCON2 never loaded it. So the assumption was that the loading process got stuck somewhere, and loading the value in OSCCON2 into OSCCON1 would make the chip think its loaded correctly. This would 'unstick' it, and then allow me to reload the correct value without it getting stuck.

This code is right at the start of the main function, after variable declarations. It solves the problem, but it doesn't explain why it was happening in the first place. If anyone knows what was causing this and if there is a better fix I'm still open to better answers.