The expression indeed comes from Henry IV as I checked on Wikipedia and saw that the title "King of France and of Navarre" starts with him and indeed stays up to the revolution.
I just find it incredible that it's still used today. You stumble upon it here and there.
I mean it wouldn't even be a valid expression if Navarre was only in France, as that would make it redundant. And since Navarre is not only in France, it makes the expression somewhat imperialistic!
I googled the exact expression "de France et de Navarre" and it returned 228 000 hits:
(a bunch of historical hits) and hits such as...
"list of hotels of France and of Navarre" "librarians of France and of Navarre" "message to islamists of France and of Navarre"
etc etc
Basically it's still used outside of purely historical applications.
