Unable to remove the mail names

[support-01]

Hi there,
I got this error when trying to remove the mail names:

Unable to remove the mail names: mailmng failed: MEAOPO.Mailbox.GetMailbox failed
MEAOPO.Mailbox.RemoveMailbox failed
MEAOAM.AddressMap.RemoveAddressMap failed for domain aliasetest.com [aliasetest.com]

I looked in the knowledge base and on the forums, I found this answer:

http://kb.swsoft.com/article_145_977_en.html

It says:

The most probable reason is that the mail box or the mail domain are not present within MailEnable configuration.
You can resolve this misconfiguration using Plesk utility:

"%plesk_bin%\mchk.exe" --domain --domain-name=<domain>

This utility will reconfigure MailEnable records in accordance with Plesk database. Then you will be able to remove this mail box.

I tried this already and it does not help. Does anybody have any idea about what's going on?

Thanks for your time.