Fix error where routes would be incorrectly parsed.

Instead of only trying the first path partition, we should check each
matching prefix slice until all path prefixes have been exhausted.

Fixes #3954