My only thought for the above is that when run as a CGI, it's running as the IIS user windows account (but when you try from cmdline you're using your windows account), which for some reason doesn't have permission to create or use the LDAP OLE object. What is the value of Win32::OLE->LastError()?
Which looks like it can't find the domain. However, when i run it from the commandline on the same box its fine.
I wonder if IIS has a setting that needs toggled to make this work. I'll start digging. This is the first time I've done anything for IIS in several years, normally I code for linux/apache.