Is there any reason why an NPC wouldn't enter or exit a cell, apart from nav mesh issues? From what I can see there is no problem with the mesh. Could it perhaps be something to do with the Location or the Loc Ref types?

Well Navmesh is usually the prime suspect, but perhaps they have no inclination to? (packages)
I doubt it has much to do with the Location and Loc Ref types.
What are your testing conditions? I think more information is required.

Idea: Are you using any "min use" doors? AI won't use those.......

*EDIT: Also, factions, and cell ownership etc.