Sorry, but as I mentioned in another comment in this post I uninstalled/reinstalled the game (and all add-ons) and that thankfully fixed the problem.
The game freezing would mean that sound/video would freeze completely (no sound stutter) and it would happen instantly when sending a message via my Xbox phone app or through the console. Doing it through my phone was interesting to see since I'm not interacting with the console menus and it locks up immediately.
When frozen, I can still access the Xbox tray menu as usual in order to force-quit the game, etc.
I'm not playing any other games at the moment, so I'm not sure if this is was Division-specific.
I'm running an Xbox One X that is one of the early ones.