It's not that hard to get an account, especially if you already exist as a customer, even a private one. The costs tend to even out over a certain volume but again, they aren't that high. I'm not sure how easy it would be if you weren't a company, didn't have an address and weren't a customer.

In Australia the most common setup is site + payment gateway (bank or 3rd party) + merchant account. If you are using some existing ecommerce software (hosted, bought or OS) it usually integrates pretty easily with large payment gateways. It all costs about 2-$400 per year plus processing fees, not much different to in store CC processing. I think it ends up at parity with paypal at around 50-$150k depending of total transaction volume (depending on transaction sizes), so you are right that it doesn't scale to micro business levels very easily.

But banks, difficult and bureaucratic as they are do compete for business clients and they do it mostly on the back of customer service.

With paypal you don't get what you pay for. If you transact $7.22 per year you get the same service as $722k.