Just because you need the 'virtual' keyword for some functionality doesn't mean you need to apply it to everything. If the find-next-location algorithm is the same for Provinces as it is for ProvinceBorders (and it should be; you can presumably represent pointers-to-neighbours internally as base Location pointers), then just put that functionality in the base class (and just accept a base Location reference for the destination).

Also, consider using references for the input parameter and return value rather than pointers (although a pointer might be useful for the return value so that a NULL indicates "sorry, can't get there from here"). In general, you prefer references at the interface level, and pointers within the implementation (i.e., as data members of a structure).