Are you, or were you ever a customer of Vodafone?
After talking about it with a few people at work yesterday, apparently there have been a lot of people who have had their details used since the security breach last year.
Both of my compromised cards have been used by Vodafone, for online purchases or bill payments.
Since one of those cards of mine is rarely used online, there weren't a lot of potential sources of breached security other than the Vodafone issue.
I'd recommend that anyone who has ever been a customer of Vodafone, if you haven't had your Credit Card compromised yet, see if your bank can issue you a new one (with a new number), stating the reason.