I had Nokia N79 Mini with Symbian.
Yes, I am from Europe, from Serbia to be exact. There are 3 mobile carriers in the country and 2 offer free video calls.
To be honest I don't know how much video calls are widespread. I don't think that people use them that much, so that is maybe the reason it is free.
Good news is that it will be somehow integrated with windows 10. Almost everyone has Skype.