These instructions are from MS's knowledgebase and apply to Access, although the error is very similar to what you're getting. I have gone through the instructions and replaced references to Access with Activesync. This is what I would try in your situation. Before attempting to reinstall ActiveSync, redownload a new copy to ensure there is no corruption in the exe.
From:
http://support.microsoft.com/kb/838983
Method 2: Manually remove the installation of the ActiveSync runtime application.
To manually remove an ActiveSync runtime application, follow these steps.
Note To follow these steps, you must know how the ActiveSync runtime application package was created.1. Remove the Windows Installer configuration information for the ActiveSync runtime application.
You can use the Windows Installer CleanUp Utility to remove the Windows Installer configuration information for the ActiveSync runtime application. To do this, follow these steps.
Important If you use the Windows Installer CleanUp Utility incorrectly, you may cause serious problems that may require you to reinstall other programs that are running on your computer. Microsoft cannot guarantee that you can solve the problems that may result if you use the Windows Installer CleanUp Utility incorrectly. Use the Windows Installer CleanUp Utility at your own risk.
For additional information about the Windows Installer CleanUp Utility, click the following article number to view the article in the Microsoft Knowledge Base:
290301 Description of the Windows Installer CleanUp Utility a. Download the Windows Installer CleanUp Utility, and then install the Windows Installer CleanUp Utility on your computer.
Caution Before you install the Windows Installer CleanUp Utility, read the instructions and the warnings.
b. Click Start, point to Programs, and then click Windows Install Clean Up.
c. In the Windows Installer Clean Up dialog box, click the name of the ActiveSync runtime application that you are trying to remove under Installed Products, and then click Remove.
d. In the Windows Installer Clean Up dialog box that displays a warning message, click OK.
2. Remove the files and the registry keys on your computer that were installed by the ActiveSync runtime application.
The Windows Installer CleanUp Utility removes only the Windows Installer configuration information from the ActiveSync runtime application. To remove the application from your computer, you must remove the files, the folders, and the registry keys that are installed by the application. To do this, follow these steps: a. Remove all shortcuts that were created to start the ActiveSync runtime application.
b. Use Microsoft Windows Explorer to locate and to delete the files and the folders that were included when the deployment package for the ActiveSync runtime application was created.
c. Use Registry Editor to locate and to delete the registry keys that were included when the deployment package for the ActiveSync runtime application was created.