FedEx Ground is estimating properly, but all other FedEx methods are coming in high (eg. up to 70% higher than what it should be for the Priority method). We have to keep giving people refunds.
All Canada Post methods are coming back lower than they should. Even after bumping them up 10% sometime we lose money on them.
UPS and DHL are working properly. This is compared against our rates shown in Shipstation.
(We've checked this with $discountshipping's all set to 0 so there is no modification to the rates.)

This isn't new, it's been a problem for years. Are the "Rating Web Services" out of date?

There are many factors/settings that impact the rates shown.
One place to start may be to dump the XML that is sent to shipping carriers by adding this parameter to your includes.php file...
$dumpshippingxml=TRUE;
...then run through a test transaction and you should get the XML displayed on the page. Then copy the XML and then take the parameter out again so customers are not seeing that.

Review the XML so you can see what is being sent off to FedEx and then see if that matches that actual shipment details in Shipstation.

Thanks,
David