It's difficult to say as we've only call the one number in France on a regular basis and that's the one we're having issues with
The problem only occurs when placing calls to the French number from both landline and mobile (both are virgin), we don't have any issues if they call us nor do the have any issues with anyone else calling them, although we're their only UK contact
We're currently using an access number to work around the issue, i.e. we initially call a UK number and use it to place the call to the French number. We don't have any problems when making the calls in this fashion, presumably because the international leg of the call is routed differently