Well.. if they wanted to, I would think it cool to simply change the jewelry, clothing, and tattoo quests already in the game to be:
A. Random reward from pool of unique items per quest giver.
B. Repeatable
This would help solve the issue with everyone wearing the same stuff for one, and give pirates that want every possible piece quests to repeat, and they need not reward notoriety after the first run, and if they do.. who cares anyways.