This needs to do what the IPV4 side does, iterate over specific then
"any" device index, doing a lookup for each case until the route is
found, therefore starting from more specific and going towards less
specific routes.

I've spoken with Tom and we can't quite seem to figure out what
exactly the code should be attempting to accomplish here.
Is checking the specific device index meant to deal with link local IPs?

As for the v4 code, I assume you're referring to ip_rt_frag_needed in
net/ipv4/route.c.

If so, shouldn't this sort of route lookup be abstracted away into
some function?
Path mtu discovery / fragmentation handling functions don't seem to be
the right place to be implementing route lookup policy.

Are you suggesting the following logic for ipv6:

rt = rt6_lookup(net, daddr, saddr, dev->ifindex, 0);
if (rt == NULL)
        rt = rt6_lookup(net, daddr, saddr, 0, 0);
if (rt == NULL)
        rt = rt6_lookup(net, daddr, 0, dev->ifindex, 0);
if (rt == NULL)
        rt = rt6_lookup(net, daddr, 0, 0, 0);
if (rt == NULL)
        return;

It's not clear to me what the last two lookups with saddr replaced
with 0 are for.

Maciej