Hello,
I have been busy with other tasks lately, but yesterday I found some time and got back to this issue. And actually I found a solution.
To put it shortly - the problem was our outdated hypervisor / guest tools. We have some compatibility issues on a few of our servers and have to hold back updates for certain packages including guest tools).
I was able to resolve the NetworkManager issue by replacing the outdated guest tool scripts with the newer ones. Now NetworkManager behaves normally.
The “fix”.
Inside the VM (with outdated hypervisor):
Replace all scripts in “/usr/lib/parallels-tools/tools/scripts/”
with the newer scripts “/usr/lib/vz-tools/tools/scripts/”
(these scripts are inside the VM with updated hypervisor).
Hopefully, this info will help someone save some time (probably not 
).
Cheers!