One idea (maybe not the best one) is to count how many subkeys exist under:
\HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall
But I haven't done the research to know exactly what gets added to the registry here. This might make the assumption that the software was installed for all users and/or that the setup added an entry to the add/remove programs.
I'd be interested to know if anyone has a better solution...