Exchange 2000 and Exchange 2003 have no problem with users (or groups and contacts) which have a space in their mailNickname attribute. Unfortunately if you try to work with one of these users using Exchange 2007 or Exchange 2010, the PowerShell cmdlets will throw a validation error similar to the following:

Property expression "John Doe" isn't valid. Valid values are: Strings formed with characters from A to Z (uppercase or lowercase), digits from 0 to 9, !, #, $, %, &, ', *, +, -, /, =, ?, ^, _, `, {, |, } or ~. One or more periods may be embedded in an alias, but each period should be preceded and followed by at least one of the other characters. Unicode characters from U+00A1 to U+00FF are also valid in an alias, but they will be mapped to a best-fit US-ASCII string in the e-mail address, which is generated from such an alias.
    + CategoryInfo          : NotSpecified: (brianlab.local...Doe, John:ADObjectId) [Update-Recipient], DataValidationException
    + FullyQualifiedErrorId : 385167D4,Microsoft.Exchange.Management.RecipientTasks.UpdateRecipient

Cleaning this up is more or less a pre-requisite to a migration. I put a quick VBScript together which will do this. The script below handles users but you can easily update the LDAP filter to grab groups or contacts as well. You’ll need to update the search base and DC at the top of the script.

Warning: This makes modifications to live recipients and if you’re running Exchange 2000 or Exchange 2003, this will trigger the RUS. I’d highly suggest doing something like an LDIF backup of the users who will be affected in case anything goes wrong.
' NAME: Cleanup mailNickname's with spaces
' AUTHOR: Brian Desmond,
' DATE  : 11/6/2010

Option Explicit

Const SEARCH_BASE = "DC=brianlab,DC=local"
Const AD_DC = "BRIAN-RTDC01"

Dim cnxn
Set cnxn = WScript.CreateObject("ADODB.Connection")
cnxn.Provider = "ADsDSOObject"
cnxn.Open "Active Directory Provider"

Dim cmd
Set cmd = WScript.CreateObject("ADODB.Command")
cmd.ActiveConnection = cnxn

cmd.CommandText = "<LDAP://" AD_DC & "/" & SEARCH_BASE & ">;(&(objectCategory=person)(objectClass=user)(mailNickname=*\20*));distinguishedName,mailNickname;subtree"
cmd.Properties("Page Size") = 100
cmd.Properties("Timeout") = 30
cmd.Properties("Cache Results") = False

WScript.Echo cmd.CommandText

Dim rs
Set rs = cmd.Execute

Dim nickName
Dim dn

While Not rs.eof 
    nickName = rs.Fields("mailNickname").Value
    dn = rs.Fields("distinguishedName").Value
    WScript.Echo "Fixing " & nickName & "(" & dn & ")"
    SetAttribute dn, "mailNickname", Replace(nickName, " ", "")


Set rs = Nothing
Set cmd = Nothing
Set cnxn = Nothing 

Sub SetAttribute(objectDn, name, value)
    Dim obj
    Set obj = GetObject("LDAP://" & objectDn)
    obj.Put name, value
    Set obj = Nothing 
End Sub