Since the persistent backend is fallible. There are expect("TODO") in there now which seem to have slipped through the cracks. It would be good to differentiate between those calls that are fallible and those that are infallible.
I think AddressIndex should go in favor of different methods that return different addresses since the error cases seem to be different.

I think with an infallible persistence backend we can have new_address but if it's fallible then it should be try_new_address and return a Result.

cc @notmandatory. IIRC you were thinking about how to redesign this.