We have HD wallets already, so a recurring payment can be from different addresses to the next bill address.
From my bank I can set up recurring transactions, but not from my wallet.
Since address reuse is not good, the payee should be able to generate a new address and send that to the payer after a payment was made, then on a scheduled time, the payers wallet can automatically send a payment to such address, and the payer's wallet bumps to it's next address for a later transaction.
The only part not implemented is attaching a next address to the transaction, preferrably encoded so only the payer can decode.
Not knowing if priv-pub keys can be used like gpg's priv-pub, but if so then that solves the encoding and decoding.
As a bonus, if the quantity needed for a payment changes each time, this information can be sent on the scheduled time from the payee to initiate the transaction.
Of course the payer should be able to block auto billing and choose their amount if they intend to pay with Bitcoin, 'cause maybe they sent a payment by other means, like in person on their way home.
This is a missing killer application. How can you expect general population to ditch banks if they can't set it and forget it like they do through their bank?