I tried to perform search by first name, last name and alias but no luck at all. I confirmed that this user has two valid AD accounts.
Since this user's extension number changed, I deleted his voicemail account with old number and tried to create voicemail account with new extension. That is where the problem started.
The Global Diretory was checked as well. There are two outputs with two userID but same extension number and same device name (MAC).
Any idea or solutions what is going on?