PayPal, PayMill, Braintree etc are all 3rd party payment
  processors. So I don't quite understand your distinction.
  I believe FastSpring may mean you avoid having to get a
  merchant account directly so perhaps that's the
  difference you see?

The main difference is that FastSpring acts as a reseller. One of the consequences being that Europe based startup doesn't need to handle VAT - technically it's selling to the US.

  The biggest objection I've heard is the 9% flat rate they 
  take vs 3% and 30 cents per transaction that you'd roughly 
  see from a payment processor.

Well, it's not cheap but we have EU regulators to thanks for it - not having to deal with VAT can be worth the price in some cases. And when a company grows, it can optimize in the payments area.