It's working now. The problem was that "Windows SharePoint Services Support" was not installed on the clients.
To install them do the following:
1. Click Start, and then click Control Panel.
2. Click Add or Remove Programs.
3. In the list of currently installed programs, click Microsoft Office 2003, and then click Change.
4. Click Add or Remove Features, and then click Next.
5. Click to select the Choose advanced customization of application check box, and then click Next.
6. In the Choose update options for applications and tools box, expand Office Tools, click the down arrow next to Windows SharePoint Services Support, and then click Run all from My Computer.
7. Click Update.
For Office 2007, you can try the same way but choose Office 2007 suite in the Add or Remove Program panel. Or try to do the following:
1. Delete the owssupp.dll from C:\Program Files\Microsoft Office\Office12
2. Run Microsoft Office Tool –> Microsoft Office Diagnostic
(not tested)
This might help someone.
Cheers,
Arno