Why not just make receipt bitfields stateful? I’m definitely cautious of automating the fee market. It requires DoS protection (as stated in your writeup) and other complexities (voluntary Merkle witnesses of state). Also, it appears to make the system more opinionated vs. a generally minimal approach. You also have less control of prioritizing your transaction in a bloated market (thereby reducing some predictability).
Running numbers on a stateful system:
To get the same effect of N = 64 (assuming the block always has 64 cross shard calls), would require 64 bits of storage for each block. Over a year, that equates to:
31536000 (seconds in a year) / 6 (seconds per block) * 64 (N) / 8 / 1000000 = 42.048 MB.
I/O would not be a significant blocker since it would be loaded in a buffer. To decrease storage further, we could likely assume receipts on average will be used within a day. This means we can limit the amount of state to ~115kb. After a day, receipts could be pruned into a separate root and witnesses would need to be submitted akin to what we assumed before (waking mechanism - Cross-shard receipt and hibernation/waking anti-double-spending). We can also significantly reduce the size (thereby increasing the stateful period) by utilizing interval trees or run-length encoding appropriately.
Maybe this is a crazy idea, but receipts seem like a fairly core piece of the protocol and seems reasonable to keep receipt bitfields stateful at least for a certain period of time.