You can check various  network-restriction options in the rightmost "Options" tab when assigning an Android profile, and  "Romaing Resrictions" configurations in Advanced Configurations associated with the device/device-group for iOS devices.

Thanks Raymond, I had not noticed that tab. Unfortunately, all of the options are already ticked.

In that case, you probably have to check the deployment server/Desployment-Server Extension log files for any clue from warning/error messages.  You might have to set the log-level of both to verbose to see more details.

Just to close the loop on this, it seems that some of the profile changes made were stopping the update from happening. I think the particular issues were swapping between normal lockdown and activity suppression lockdown. Reverting to a previous version of the profile was possible and then I was able to revoke the profiles. 

It just turned out the phone this first occurred on was roaming at the time. After a bit of testing it also started happening with devices on WiFi.