A small tl;dr for those that haven't used or looked at BitcoinNotify: they offer a service where they can monitor an address in the blockchain for you and send you a notification (for example in the form of a callback to a script on your site) so that you can be notified of successful payments *without* having to trust a third party with your Bitcoins.
Now the obvious issue is that BitcoinNotify would be able to make fake callbacks to make transactions 'go through' that never happened - because, let's face it, people are paranoid about things to do with money. I'm not saying that the people behind BitcoinNotify are untrustworthy, but let's just assume for the sake of this proposal that they would send out fake callbacks.
My proposal is a very simple one - more of these notification services. Independent services that all do roughly the same, making a (double) callback when a payment is seen to be received. Now the trick would be to require a callback from all of the notification providers before a payment actually 'goes through' (or almost all of the providers, to cope with providers that suffer from downtime). Someone would have to have access to all of these providers to make a fake notification go through.
Possible issues I see:
1. Taking out all of these notification providers with a DDoS attack would effectively disable someones ability to process payments - but then again, this is the same for a payment gateway (which would have a single point of failure, unlike this proposal).
2. Notification providers may disappear over time, and new ones may appear, meaning a business owner has to maintain some sort of list of notification providers.
3. To successfully pull this off, some sort of standard would have to be created for Bitcoin payment callbacks.