Getting a "Please Specify a Shipping Method" exception during checkout

You have to understand how the rates work and how they are requested. Basically rates are requested when ->setCollectShippingRates(true) is set on shippinAddress object and it result rates to be collected and stored in rates table. This table is emptied afterwards and filled again on new rate request.

what is happening in your case is that error is thrown and request is repeated and rates are not requested but are expected to be there. So try and force the rates collection over

getQuote()->getShippingAddress()->setCollectShippingRates(true);

and then try to recollect totals as well if it does not work

getQuote()->setTotalsCollectedFlag(false)->collectTotals();

be warned that calling collectTotals multiple times can mess up your totals if some extension does not implement totals objects correctly (a common flaw)

Might have figured this out. I had a related exception that was being thrown with about the same frequency as this one, which was "The requested Payment Method is not available".

Turns out that the reason it was happening was because one of my observers off of sales_place_order_after was creating a quote object (and saving it) in order to generate some subscription pricing.

I was able to get it to reproduce by first checking out with a bad credit card as a new customer (not logged in), then going back and fixing the credit card and attempting to checkout again.

The exception was throwing because in the loadCustomerQuote observer of customer_login, it will merge your quotes together if you have more than one quote, and in so doing it loses some of the payment method information on the quote.

The fix was to delete the new quote that I was creating in my subscription observer.

UPDATE: Nope, the fix for "The requested Payment Method is not available" didn't resolve this issue, still occurring.