The capability of self-driving cars to relocate occupant-free is suggested to become one of the most disruptive yet beneficial features in the era of fully autonomous vehicles (FAVs). One relocation option is cruising: Once arriving at the destination, a traveler may instruct her FAV to circle around to bridge the time span between drop-off and pick-up, implying no need to park at all. This seems promising, given the various inefficiencies associated with parking. In this paper we show that driverless vehicle cruising is accompanied by its own inefficiency and, thus, should be a major issue of concern. By developing and applying an integrated economic equilibrium speed and parking choice model, we identify the counterpart of the classical (negative) cruising-for-parking externality in the world of non-autonomous vehicles, namely a (positive) speeding-when-cruising externality that may occur in the era of self-driving cars. The externality emerges because driverless vehicle cruising entails moving at very low speed, thereby imposing congestion on regular (non-cruising) traffic. We show that when not accounted for by cruising FAVs themselves (e.g. via a Pigouvian speed subsidy), not corrected through regulation (e.g. via speed control) or planning (e.g. via dedicated lanes), the traffic system fails to achieve a socially optimal outcome. When parking-as-a-substitute-for-cruising is feasible and properly priced, a welfare-maximizing speed regulator would enforce cruising speeds that deter travelers from choosing inefficient cruising. In this case, welfare is improved and parking would be even socially desirable (at least in the short term). However, when parking is free and parking externalities are substantial, the transport system features too many parkers, but to limit the efficiency losses in the parking market, socially optimal speed regulation enables cruising too. In that case, the result is a huge welfare loss even with regulation stemming from traditional cruising-for-parking induced by parkers, and road congestion caused by cruisers. Our findings support the idea of adopting economic instruments, planning tools, command-and-control approaches, and parking-as-a-substitute-for-cruising to tackle the potential inefficiencies resulting from driverless vehicle cruising, but also underscore the inappropriateness of parking-as-a-substitute-for-cruising when it is heavily underpriced.