The problem with this is that most traditional sandwich veggies have a short enough shelf life that it'd be silly for me to buy them - they'd go bad before I remembered to use them

Insofar as remembering is important, this might be relevant: I'm experimenting with actually writing up menus for myself in advance. So far it seems to be helping me remember to use up all my vegetables.

There are also veggie-intensive sandwiches. I don't think it would take very many hummus and cucumber sandwiches to use up a small cucumber, for example. A whole red pepper can probably be used up by 2 sandwiches, especially when roasted. Same with avocado (minus the roasting). And wraps can materially increase the veggie-to-bread ratio; you could probably use a whole avocado in a single wrap.