As more European roads become tolled by various means, an increasing share of road users become subject to more than one tolling scheme in their regular driving. This can be especially burdensome for long distance hauliers, who may pass several countries and tolled motorway systems during the course of 1 day. For this reason, a range of projects have been initiated attempting to increase the level of interoperability between tolling systems, many of which with only limited success. By analyzing current incentives, costs and benefits for toll operators and road users, we conclude firstly that the current level of interoperability is likely to be lower than socially optimal, and secondly that a direct regulation making the provision of interoperability mandatory is likely to be in excess of what is socially optimal. We argue that vertically separating the monopolistic toll operators could be a cost-efficient way to achieve a socially optimal level of interoperability as a equilibrium market outcome.