@cstrossObviously, this depends on what resources are (not) available. Time might be a good one (some recipes take three reincarnations to complete properly -- my family were all brought here so that centuries in the future, this one dish can be used to celebrate the anniversary of X). Tastes will probably have changed, but if the point is to show wealth, that may not matter.
Foods that aren't just fermented but aged (cheese, fermented tofu) -- especially if they're part of the sauce or otherwise not the main focus of the dish, but still noticeable. Mummified meats from previous civilizations (even if you've revived the species, maybe it's still hard to work out what all the aging processes are). Sauces derived from the slow fermentation of ancient plastics (depending on metabolisms) whose exact composition is lost to linkrot.
If there's much space colonization, possibly some delicious fungus evolved in the messes you find in air filtration units, or were created as part of atmosphere maintenance (what good is a life support system if you can't eat every part of it?) You might get centuries old scoby treated like prized sourdough starter.