How to get specific recommendation on such a wine? I have seen this description but do not know which wine could this be.
Strong pigments in red wine are instant stain-makers for porous surfaces like your teeth. These pigments, called chromogens, give it that deep, intense hue, and leave their mark on your teeth after just a few sips. The nature of enamel plays a big part in this process. "Enamel isn't perfectly smooth," says Benjamin Rudow, D.D.S. "It has small cracks and irregularities, and pigmentation from red wine will settle in them
So you need to seek out wines that have the highest amount of tannins possible. Your run of the mill grocery store wines will not have a lot of tannins because it's more work and that makes the wines more expensive. Wines meant to age a long time will usually have more tannins since they help buffer the effects of oxidation and help the wine last longer.
So, really you want expensive, long lived, tannic wines. Those would be Cabernet, Petit Sirah, Tempranillo, Nebbiolo. But if you really want to go full stain, try a Tannat wine. It will stain your lips, gums, teeth and tongue! It's hard to find a 100% Tannat, but there are some that make it.
Tablas Creek in California makes a 100% Tannat that I've had before and it will stain like nobody's business!