PA-DSS compliance is a major roadblock for ecommerce startups, what to do?

The workaround is to integrate with someone else's certified application.

Unless, of course, you plan to compete directly with one of these packages in which case the 40K is a cost of doing business.

There are lots of business you can't start on a shoestring due to regulatory costs, or requirements for multiple employees. (You can't start a bank, an insurance company, or a supermarket without capital and multiple employees either.)

Such is life.

I know this is a non-answer, but: Complain to your Congressman that the fat oligopolies in the credit card industry are pushing their problems onto the little man, instead of doing their own work themselves.

I have a Danish credit card, which is really 2 cards in one: A local "Dancard" and a Visa card. The Dancard uses modern smartcard encryption systems, and I have never seen fraud on this card.

My Visa and Mastercards on the other hand -- there is fraud something like 1 out of 3 times that I travel to less industrialized countries. Why? At least in part because a Visa or Mastercard uses 1970's technology, which is trivially easy to hack today.

But PA-DSS is a symptom of people growing tired of credit card fraud. Even if the entire card technology stack was modernized overnight, I would still expect the rules around personal information handling to be tightened. If you are in the business of developing and selling payment solutions, then I think you need to adopt to tighter regulation and higher development costs, or leave the business.