Message deletion problem in Exchange

Since yesterday I started having problem deleting multiple messages from either Outlook or Exchange client (from any mailbox). I can delete message one by one with no problem, but if more than one message were selected, the application just hang, the deletion box comes up and keeps going without doing anything. I tried restart the Exchange Server (5.5) but didn’t help. Your help will be greatly appreciated.

dave