We had this problem in my environment. Th sync between enterprise directory and
the sharepoint DB wasn't working automatically as it should work.
When contacted Microsoft, they said its a design flaw. Not sure about your
environment. Better log a MS call.