Good question. It isn't a problem I've thought a lot about but I think something like my idea for off-chain messaging with on-chain fee payment is probably a good foundation. Listing items, making offers/purchases, etc. could all be messages. Identity, rating, reputations, web-of-trust, etc. are a tricker problems and probably need some other solution.
Search is unsolved, and openbazzar got a lot of things about the infrastructure obviously wrong (running over UDP which is incompatible with Tor - WTF?, people need to leave their computers on to serve a store - WTF?)
I think it should be left off Monero's blockchain for reasons stated by Smooth in the past about the potential to "bloat" the chain or whatever...
I just think that this theoretical store would need people to run it's own software program and have it's own GUI and everything... like downloading, running a node, and web browsing through tor, in a way... I would assume...
The off-chain message proposal is a good model, in principle. It includes a mechanism for paying a fee on-chain (after all that's the only way you can pay a fee), but the content and most of the interaction is off chain. Even that might become unscalable if the volume of usage is extremely high (so too many fees being paid) but we can address that if and when it happens. For now the bigger issue with Monero is empty blocks, not too many transactions.
3 month bump!
@Smooth, are there any flags that could be set so that the added bloat could be temporary and pruned after a specific time frame or would a HF be required to add one? My mind is weird, I just remembered I never asked this question (I think I took off for a week and forgot about it)!
If I recall correctly my off-chain message proposal could be implemented without a hard fork. It does require nodes to upgrade, or alternately a completely separate program could be used to transmit the "payload" (perhaps in the case of a commerce application this would be a better approach anyway).
As far as Monero stands today, there isn't really any way to put data on the chain that can be completely pruned. Limited pruning of signatures like what Bitcoin currently does (only storage, not addressing bandwidth) can be done with Monero as well (similar to what is implemented in AEON, but it would need to be redone for LMDB). As I understand it, things are reworked a bit in RingCT and more modes of pruning may be possible, similar to Bitcoin's segwit. I have not followed the coding for RingCT closely though, so I don't know the details.