What you can do is throwing away the internet mail service under connections. Stop the system attendant service, so all other exchange services stop. After they have stopped restart them. Then create a new internet mail service (by deleting this service starnge object are removed.)
If this is not yet the solution you may have a corrupted database.
You can take the exchange server offline and try to repair and check the database. Microsoft Exchange Server 5.5 includes a utility called Eseutil, this utility can Defragmentate, Recover, Check Integrity, Upgrade, make a file Dump and Repair a corrupted database.
By repairing and defragmetation you can regain your speed. If the database is for example 2Gb in space you will need at least2GB free space for a repair and an defragmetation.
For more information about eseutil see technet article Q182903.
good luck.