I am going to suggest something completely different (and not really what you asked for). Try gin. I prefer a bloody mary made with gin, particularly Tanqueray. If they can make martinis with vodka, we can make bloody maries with gin.
BTW, I saw an interesting comment once on the recent focus on flavored vodkas. It sort of went "if we keep this up we may well invent gin".