The basic difference is that な is gradable and の is not. For example, consider the word 最低. It has two meanings: “the lowest” and “(to have) terrible character”.
You cannot say 最低な to mean “the lowest” (a clearly binary attribute: it is either the lowest or not), it can only mean “terrible” (a potentially gradable attribute: there are degrees of terribleness). So *最低な点数 is weird (barring really odd scenarios).
最低の on the other hand works with both meanings. This means that the "terrible" meaning can be accessed with both 最低の and 最低な. I think if you say 最低の男 with the “terrible” meaning it feels a bit more like “the worst guy ever”, as opposed 最低なやつ which feels a bit more like “a guy with a terrible personality”. That said, it’s a faint difference.
This works with other の/な-compatible 最 adjectives like 最高 too. Is it the best (binary, の) or awesome (gradable, な).
I think it’s best to understand this as an evolution, where the words started as の adjectives, with only their literal “lowest” and “highest” meanings, then they took on the extra meanings which feel more gradable, and as a result started accepting な as well, but the の also remained usable.
With other adjectives like あいにく, it’s not quite as clear, because there's only a single meaning to the word, but I think the same distinction holds. And importantly, I feel like an extension of the distinction is that 〜な, due to being gradable, feels more like making a judgment call about something — it’s more of an opinion or feeling. 〜の feels more like a “fact”, because it’s claiming that the referent is 100% that attribute.
So taking two examples from 大辞林, 「あいにくなお天気です」 feels more like “ah the weather is too bad isn’t it” (too bad = opinion) while 「あいにくの雨で一歩も外へ出られなかった」is more like “due to the (unequivocally) unfortunate rain, I couldn’t take even a single step outside”, where there is little room for discussion about whether the rain was unfortunate — it was 100% unfortunate from the perspective of the speaker.