you could have an 80 pettabyte pipe, but the mail server probably has restrictions on the size of email it will handle, so it makes mail seem slow. Its not mail apps fault.
.Mac does not sync your actual mailboxes. You need to back these up withe another program.
after backing up your mailboxes, I would delete old unneeded email.
I would try what analogika said...rebuild all you mailboxes. I would also erase deleted messages (you'd be surprised how many people overlook this).