Use Acrobat's "Optimize Scanned PDF".
For Acrobat 9 Pro use Document > Optimize Scanned PDF
Set "Deskew" to automatic.
Acrobat X has a similar feature.
I tried this with Acrobat X Pro and document did not deskew. Tried with Acrobat 8 on a different workstation (same document) and worked fine. This is not a newly scanned document. It is a mechanical fax received as PDF with an online fax server.