They should be titular now and given enough time they could be redejured into existence.
However the chances of that, unless the player is directly involved, not even through vassals(they'll war each other over dejure lines) is virtually non existent.
Hence why I propose for "historical" kingdoms be decoupled or immune to drift, especially for Andalus, because you either get a completely ahistorical blitzkrieg reconquista, or the Iberian peninsula is screwed up forever.
And if that happened, you could end up sitting there holding all of the Iberian Peninsula under your Navarra kingdom, but never getting the provinces de jure. That'd just be crap. To be honest, it'd be even worse than what we have now. :/