I know it's a commercially available option, but Conor Kerr's Advanced Shipper module will solve practically EVERY shipping conundrum zenners face.

http://dev.ceon.net/store/index.php?...=index&cPath=1