Hi, No, I get it - you aren't ordering them: OZ plumber seemed to suggest you should do this and my disagreement was with his suggestion and not what you had written.
You'll note that if their waste pipe encroaches on your land, so does their rainwater gutter!
I doubt the pipe will prevent you gaining planning permission. Even if the pipe is on your land, I would imagine (at worst) you'll have to re-route it as others have suggested. Having sat through a few planning meetings (they can be quite amusing), I've seen it before where a neighbour has raised a large number of possible objections to a development - none of which were valid planning issues - and where the development has been approved nonetheless. Sometimes neighbours get funny if you contact the planning office before discussing with them, but some people aren't worth discussing with and will object for the sake of it. The planning committee will be used to this sort of thing, so don't let it put you off.
As far as your neighbour's objection is concerned, try to let them see that you take their objection as their doing their civic duty in informing the planning office of all circumstances they feel relate to your proposed development and, after all, it is the planning office that makes the decision. In theory (not always how it works, mind, especially when the number of objections becomes a political force), the planning office should ALWAYS block an unsuitable development even if the neighbours like it, just as they should ALWAYS allow a suitable development that a neighbour objects to.
As far as the presence of an easement or not being noted on the deeds is concerned, I'm not sure how that would apply to services of this nature, otherwise my neighbour could insist that my water supply pipe (under their garden since at least 1961 and which neither of us knows the exact route of) be removed (there must be millions of similar cases), which makes little sense in the light of a right obviously acquired by prescription if not by any other mechanism. The answer is, if this is going to become an issue, you need legal advice (tip: you may well have a free legal advice helpline included in your home insurance policy or trade union menbership).
With regard to a potential toilet waste leak, well, it's obvious your neighbours must maintain that pipe so that it does not leak. Obviously the neighbouring roof must also be maintained. A leak is possible in the same way as it is possible that a slate could fall off their roof - it should not happen, but the fact that it could happen if something went wrong is not a reason to remove that part of the building.
Now you mention a smell, however, the question is whether is comes from the open vent above the roof (which could be normal if that's the only open vent which serves several houses including possibly yours: your drains may well be interdependent) or whether the horizontal pipe is leaking. If, as I assume, the first time you mentioned the possibility of a leak to your neighbours is after you started considering building where the pipe now is, this is unfortunate: the neighbours may now think you're making the whole thing up which is most unfortunate. It may be worth a call to your council's Environmental Health officer for suggestions.