Mail.app 5.1 is unusually slow
You might try the following:


Quit Mail first
Run the following command in Terminal: 

sqlite3 ~/Library/Mail/V2/MailData/Envelope\ Index vacuum;


This will rebuild your Mail index data.

Below is the actual shell script that I use. I keep it in ~/Library/Scripts/Applications/Mail so it is accessible from the AppleScript menu in Mail.app

#!/usr/bin/env bash

mail_data_dir="/Users/$USER/Library/Mail/V2/MailData"
killall -HUP Mail
BEFORE=`ls -lah $mail_data_dir | grep -E 'Envelope Index$' | awk '{ print $5 }'`
/usr/bin/sqlite3 $mail_data_dir/Envelope\ Index 'PRAGMA integrity_check';
/usr/bin/sqlite3 $mail_data_dir/Envelope\ Index vacuum;
AFTER=`ls -lah $mail_data_dir | grep -E 'Envelope Index$' | awk '{ print $5}'`
echo "before: $BEFORE"
echo "after:  $AFTER"
open -a "Mail.app"
/usr/bin/osascript -e 'tell application "Mail" to display dialog "Envelope Index before: " &amp; "'$BEFORE'" &amp; return &amp; "Envelope Index after: " &amp; "'$AFTER'"'


When run it will automatically quit Mail. Run the command to rebuild and check the integrity of your Mail index data, restart Mail and present a dialog box showing you the before and after sizes of your Mail index file.