Another approach is to have "trusted sources" which are Bitcoin banks/ewallets. If your customer is using a Bitcoin bank like eWallet to send a payment, you can pretty much assume that the transaction is valid based on the source, without verification.
Either way, this is merely a short term problem. As more Bitcoin infrastructure springs up (more banks, more verification hubs, more incentive on transaction fees rather than mining, when mining gets too expensive) then these problems will be organically mitigated. If the Bitcoin infrastructure were to remain the way it is now forever, it won't scale for many other reasons (like requiring peers' wallets to store significant transaction history that could grow at the rate of gigabytes per hour with "real world" volume).