I had a Pearl and just updated to a Storm and never had any of the problems you describe. At that, when I updated to my Storm, it was three clicks and I was done (Outlook sync with redirector, no problems).
Do you think you may have tried to set up with the enterprise service versus the redirector initially which started the process off wrong?
No, The redirector and Desktop Manager was recognizing the phone. I was able to do a backup, and was able to set up sync through Outlook Express, Yahoo or an ASCII file once I installed the earlier version. But I still couldn't get the Outlook conduit recognized until I upgraded the phone's software. If I tried, the applications manager would tell me there was no applicable installer app on the phone (or some such message). I like the little phone (well, except for the default text entry method which after some time I figured out how to circumvent). It's just the desktop manager application that I think leaves a lot to be desired. Are you using newer versions of Outlook? I understand Outlook 2003/2007 sync well with the newer versions of desktop manager. It's just the older versions that are a problem unless the registry is changed (no big deal on that...)