Edit Deux: Never mind, I found the problem. I only looked under one registry key, but found balloon tips disabled in a second registry key.
For future reference, here is where I found the value in question:
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\Advanced\EnableBalloonTips
2.5 years later this is still very helpful. Thanks a lot for the answer.
It should definitively be in a FAQ or as a sticky