@Jan De Smet Based on my understanding, android enterprise enrollment is needed to connect your Intune tenant to Managed Google Play. When you disconnect the deleted google play account, it will occur a message "Please unenroll all Android devices with a work profile."
https://www.azure365pro.com/disconnect-managed-google-play-account-in-endpoint-manager/
To avoid any strange issue occurring, it is suggested to retire android devices, link the new google account and re-enroll the devices.