I haven't encountered this issue myself, but I have some theoretical knowledge that could be of assistance. 

There are two things involved here that cause this issue:

1. The ShippingDiscountAmount field on Shipment level.
   This is accessed in code by calling IShipment.TryGetDiscountValue(x => x.ShipmentDiscount)
   This is set while running the promotion engine. But can also be set manually by doing IShipment.TrySetDiscountValue(x => x.ShipmentDiscount, 1337m)
   
   
2. The method IShippingCalculator.CalculateShippingCost(IShipment shipment, IMarket market, Mediachase.Commerce.Currency currency)
   This is used to calculate the current shipping cost, so it basically takes whatever value you currently have set in your shipping method configuration.

The value taken from the "static" ShippingDiscountAmount field is then subtracted from the, in your case, dynamic value that comes from your shipping method configuration. If the latter is lowered it will of course be negative as you figured.

The "static" field in this case is reset by running the promotion engine, but keep in mind that this might change the order total in other ways as well, for example if you have an order total based promotion that would no longer be valid or if a promotion has passed it's valid date.

In QuickSilver the PromotionEngine is probably run at some point after you change the shipping methods' cost.

The simplest solution would be for you to see if there's an appropriate way for your impementation to run the promotion engine before doing the actions that generate the error.

Thanks Jeff that all makes sense!

Unfortunately I wasn't able to figure it out by running the PromotionEngine since the error only occurrs after the order has already been completed and saved as a purchase order.

Instead, I've solved it by overriding CalculateShippingCost on DefaultShippingCalculator, where I just use the base method but check the return value agains the discount to see if we're gonna end up with a negative value.

Nice! Care to share your solution for future visitors? :)

I also found this topic a bit interesting in other regards because I don't think the promotion system + DefaultCalculators are truly compatible out of the box with this type of reconfiguration. But maybe I'm missing something. :)

It does touch a bit upon some business rules because depending on what type of discount you've applied to shipping costs we could end up calculating the order total to less than what the customer originally paid.

For example:

Shipping Cost = 40NOK
Discount Rate = 50%

When order is placed we have a ShippingDiscountAmount = 20NOK

Shipping configuration changes to have a shipping cost of 30NOK


Now when we calculate the shipping costs in DefaultShippingCalculator we end up with a shipping cost of 10NOK instead of the original 20NOK.

I'm not sure if this can have a negative effect on your solution (and when you press the button that you got your current error on) but it might need some additional handling.

For example, ensuring that you do not get the shipping costs dynamically from the shipping method configuration after a certain point when we know that the shipping costs shouldn't be allowed to change.

@Jafet: I seem to be having the same issue in Commerce 12.10.0 as well. I have the same exact stack trace, below is the code snippet from my solution that triggers the exception:

if (cartService.AddCouponCode(cart, CouponCode))
    cartService.SaveCart(cart);

    public virtual bool AddCouponCode(ICart cart, string couponCode)
    {
        bool returnValue = false;

        if (couponCode != String.Empty && couponCode != null)
        {
            var couponCodes = cart.GetFirstForm().CouponCodes;
            couponCodes.Add(couponCode);

            var rewardDescriptions = cart.ApplyDiscounts(ServiceLocator.Current.GetInstance<IPromotionEngine>(), new PromotionEngineSettings());
            var appliedCoupons = rewardDescriptions
                .Where(r => r.AppliedCoupon != null)
                .Select(r => r.AppliedCoupon);

            var couponApplied = appliedCoupons.Any(c => c.Equals(couponCode, StringComparison.OrdinalIgnoreCase));
            if (!couponApplied)
            {
                couponCodes.Remove(couponCode);
            }

            returnValue = couponApplied;
        }

        return returnValue;
    }

Attached is an image link: https://www.screencast.com/t/rMSqLkX6

The coupon code applied is a free shipping coupon code. The one on the left works fine if I add 4 items of the same SKU. But when I add just one it fails. I am having a custom shipping calculator as well. I see that upon save it triggers all the calculators and then end up failing. Dont you think this is a bug?