Slow Mail.app in Lion OS X 10.7

I recently helped a client with a terribly crippled Mail.app on their Mac. They had upgraded to 10.7 (Lion) from 10.6 (Snow Leopard) not long ago and are a heavy user of Mail.app. Unfortunately, as seamless as upgrading OS X often is, installing a new system over an existing one sometimes brings current issues along with, or create …