Small ISP, many service blocks. What to do?

Hi all,

I work for a small FTTP ISP. We recently purchased some new IPv4 blocks, notably some from the less popular parts of Europe. We had many customers complain that their IP was showing up as being part of those unfavourable countries, and thus they couldn't access many UK services such as BBC iPlayer, or even websites like nectar.com.

I have already made a significant effort to correct as much of this with big fraud database providers as possible, such as MaxMind and a few others, however this has not done much for us.

If you were in a situation where a handful per hundred of customers in a small customer base were being affected by such a problem, how would you look to deal with it?

As far as I am able to see, all of our IP blocks are properly set up in RIPE with the UK as our country, and MaxMind and a few others are returning the correct country.

Thanks.