10.5.7 Mail painfully slow - need help to diagnose issue ?

37 MB is very small for 5.9 GB of mail. I guess you must have lots of attachments taking up the space, rather than lots of messages. Mail should certainly be able to perform well at that size.