For what it's worth, this also happens in Canada on Rogers Samsung Galaxy S6 running 6.0 with WiFi calling. Just updated to Nougat and space not cleared. Factory reset is still the only solution.
http://forum.xda-developers.com/galaxy-s6/general/apk-s6-quick-panel-restore-t3137253 Worth a try... No idea if it will fix your specific requirements.
Waze is very CPU hungry and I find that it very quickly sucks the life out of the battery. If it's competing with other applications, it might well lag.
It's almost impossible to securely erase a flash based memory system. If you had root access, you could scrub it with random data at a device level but even that will not erase blocks that have been mapped out as "defective". How paranoid are you?
This is all pretty stupid, not having an OTA update service that can actually accommodate those end users that can't run Smart Switch for any reason, (like me, for example).
Does the Bluetooth car system have it's own GSM radio system? If so, it might be taking over the SIM card in the phone rather than using the phone to handle the radio interface. Check the type of pairing that you have set up.