Have Bechamel (the accessories NPC) sell the most basic accessories in the standard colors much like Sullivan sells a set of standard Bombhead masks. Because there would be so many possibilities due to the combinations of color and accessory type, have her (is Bechamel a she?) carry only a finite number of accessories at a time, much like Vatel's randomized inventory. These would be sold for something- crowns, ce, mats, whatever. Perhaps 500ce apiece would be reasonable, given that you get to choose your piece, but you forfeit the odds of getting something much more awesome.

Rarer accessories- like regal/volcanic/prismatic colors and auras/glasses/scarves would still be obtainable only at random from lockboxes. This would allow everyone with a moderate amount of wealth to accessorize their character, while still providing the currency sink that OOO wants. The rich players are still going to go unlocking boxes to find that awesome accessory, but mid-level players will be able to spiff up their characters a bit by patiently waiting for Bechamel to sell the accessory they want, thus making everyone happier without costing OOO too much.

The final suggestion is to have accessories bind to the player rather than the item; include accessories in the Loadout. If you equip a different piece of costume armor that does not have a spot for the accessory, it is automatically de-equipped. A side effect is that the rarity of accessories would have to increase, and the cost of purchasable accessories would have to go up (since you only need one piece now, instead of one for each of your helms/armors).