Navigation service: fix parent search for naventry

A regression was introduced in e346da8a, causing all backtracks generated by this service to be invalid. While iwe're add it, add a few tests as well.

Please note this does not fix issue #1153 (closed), but at least this patch paves the way forward to fixing that issue.