This project is cool. You've obviously thought way harder about this problem/solution space than I, but something to consider if you haven't already...

Could the hosting cost be dramatically reduced if everything was deleted by default after some per-post-configurable amount of time?

Keeping data would become a reason to build an extension. Rather than the other way around. Relays would have retention policies. Users would have re-broadcast/archive policies. Those could be co-operative or redundant, depending on their respective choices and indexing extensions installed. The rogue relays would be the ones intentionally keeping data longer than they are supposed to, which would be kindof a service in and of itself.

...anyway, just $0.02 for you to noodle on. Keep up the cool work!