Which wines have a strong, bitter flavor? I experimented with adding wine and dark chocolate to a sauce. The result was generally OK, but the wine was not strong enough in comparison to the chocolate, I would have liked more of its taste to come through. 

I knew that I will need a strong, assertive flavor for this combination, so I got a bottle of dry Cabernet Sauvignon, the label called it "spicy" and recommended it for dark sauces and beef dishes. But when I tried the wine, it turned out to be OK in taste, but too light for this application. I would have liked more bitterness and earthy notes, less fresh/sour taste. 

What could have helped me find such a wine? Which grape variety (or region, for wines sold by region) would have been a better choice? Are there other signs which would have indicated such a taste? For example, I know that a Gran Reserva wine is supposed to have a better, smoother taste due to better production, but would it also have predicted a wine with a heavier taste? Would barrel-aged wine have had that taste? 

If possible, I would like to hear about European wines, because I pay less for an European wine than for the same quality imported wine. But if you have continent-independent advice or can only name wines from other continents, that's still OK, there are lots of imports here.
I haven't cooked chocolate with regular wine per se, but my instinct is that to get the right marriage of flavour you really might need to consider alternative approaches with both a higher sugar and alcohol content: dark chocolate is a very powerful flavour that will obliterate most wine.

So I would try using something else wine-related but with a considerable higher sugar and alcohol content: Port and chocolate certainly can complement each other well - I would recommend a tawny port (I have used this combination as a sauce for a savoury dish). You might try sherry too, but this is slightly riskier territory in my opinion.

A further alternative depending on the dish you are cooking would be to pursue your current course add a third component that will help with the overall flavour structure, typically something bittersweet and with fruit, such as redcurrant jelly.