There are a few things that can cause this error. In many cases it's related to an invalid character in an attribute on-premises. If you have any users that exist on-premises with one name (perhaps with an added space), and in the cloud with another name, this can occur. Check to see that none of the UPNs have extra spacing. Would you please go to the on premises directory, and check for any extra spaces or invalid characters in the UPNs of your users? Once you finish you can start the sync cycle by using the Powershell cmdlet Start-ADSyncSyncCycle Delta
If you can provide a screenshot of the error in your logs, it may help us narrow this down more.
I have also seen this happen for users that have had empty subscriptions set up. You can run "Get-AzureSubscription -default" to see what your default subscription is. You can then "remove" any empty subscriptions using the "Remove-AzureSubscription" command.
As you mentioned, sometimes a full uninstall, cleanup, and reinstall is required to get past this error. If you do this you need to delete all references and folders. This might be a last option as I understand that it's a pain, so we should probably rule out the other options first before doing this.
In this case you would need to uninstall all instances of Microsoft SQL LocalDB, Microsoft SQL Native Client and Azure AD Connect.
You'll probably need to use the Microsoft program uninstall fixer tool to accomplish this.
After doing the above, delete the program files located at:
%ProgramFiles%\Microsoft Azure AD Connection Tool
%ProgramFiles%\Microsoft Azure AD Sync
%ProgramFiles%\Microsoft Azure Active Directory Connect
You will need to stop the "AD Sync" service. Otherwise, it wont let you delete some of these.
Remove the following registry keys:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\AD Sync
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Azure AD Connect
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\MSOLCoExistence
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Microsoft SQL Server
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Microsoft SQL Server Local DB
HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Services\ADSync
HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Services\EventLog\Application\ADSync
HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Services\EventLog\Application\AzureActiveDir
ectorySyncEngine
HKEY_LOCAL_MACHINE\SYSTEM\ControlSet002\Services\ADSync
HKEY_LOCAL_MACHINE\SYSTEM\ControlSet002\Services\EventLog\Application\ADSync
HKEY_LOCAL_MACHINE\SYSTEM\ControlSet002\Services\EventLog\Application\AzureActiveDir
ectorySyncEngine
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\ADSync
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\EventLog\Application\ADSync
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\EventLog\Application\AzureActiv
eDirectorySyncEngine
HKEY_LOCAL_MACHINE\SOFTWARE\Classes\AppID\EventLog\Application\ADSync
HKEY_LOCAL_MACHINE\SOFTWARE\Classes\Installer\Products\
Finally, reboot the machine running Azure AD Connect that we've just removed, and you should be able to install it as normal.
If you think it might be easier, you can also send me an email at AzCommunity@microsoft.com and I can open a one-time free support case to help you troubleshoot this.