Existe uma propriedade para objetos de usuário (todos os objetos realmente) no diretório ativo chamado objectGUID. Você pode consultar isso a partir do diretório ativo e armazená-lo no banco de dados com o perfil do usuário. Ele é inteiramente exclusivo desse objeto de diretório ativo e não será alterado se o nome mudar.
EDITAR:
Amostra:
Private rootDE As New DirectoryEntry("LDAP://<YourDomainHere>")
Dim ds As New DirectorySearcher(Me.rootDE)
Dim sr As SearchResult
ds.Filter = "(samAccountName=<usernameHere>)"
sr = ds.FindOne()
Dim s As String = Me.GetGUIDString(CType(sr.Properties("objectGUID").Item(0), Byte()))
Dim de As New DirectoryEntry("LDAP://<GUID=" & s & ">")
MessageBox.Show(de.Name)
Private Function GetGUIDString(ByVal guid() As Byte) As String
Dim index As Integer
Dim result As New System.Text.StringBuilder(String.Empty)
For index = 0 To (guid.Length - 1)
result.AppendFormat("{0:x2}", guid(index))
Next
Return result.ToString()
End Function