Hi Marco - sorry for only replying now.
We are using an earlier exchange domain, so completely non-powershell. I'm only posting in case any other folks are having the same troubles.
Basically, only 2010 (I think) at the moment is PS compliant and trying to use powershell on the older versions will not work, unless you upgrade your entire exchange, which will not happen in most circumstances.
In my case on this thread, I used powershell to create the users and VB to create their mailboxes...
It's unfortunate that Microsoft has cut PS off from earlier versions. But money talks I guess!