I have googled, but it is difficult to judge the services that come up. (Edit: just found that Idology seems to verify based on street address - good enough for a mail order company, I guess, but probably not for access restrictions to a web page?).
It is of course a legal question, but also a technical one. For example it is a technical question if I can determine the country my user is coming from. I suspect not, though (user could use proxy in other country) - or at most, one could determine a probability and then it would again become a legal question.
I am fairly certain that it is possible to determine country by IP. I have seen this done before in several cases: some products with encryption are illegal to "export", and thus restrict the IPs that can access them. Also, I have seen the same for content providers who only have a license for a certain market (specifically I have seen a Japanese company restrict their content to "Japanese IPs").
You make a good point about proxying through different countries, but I don't think in you would be liable for that. Often these things work on some sort of a "reasonable effort" type clause, because its impossible to verify with complete certainty someones age programmatically.
Perhaps asking them trivia about music that was in style two decades ago...
It is of course a legal question, but also a technical one. For example it is a technical question if I can determine the country my user is coming from. I suspect not, though (user could use proxy in other country) - or at most, one could determine a probability and then it would again become a legal question.