I installed ImageMagick-6.7.4-4-Q16-windows-dll.exe on Windows XP. In case it matters, I unchecked all of the check boxes.
Convert.exe would work for the user which performed the install but not for other users.
I eventually found the problem was that the registry entries were under HKEY_CURRENT_USER\Software. I moved them to HKEY_LOCAL_MACHINE\Software to fix the problem.