After scanning the entire internet and still failing, I finally figured out a way to fix this. And now that I think about it, the solution seemed sort of obvious. Hopefully, this post will save another poor soul like me.
The Problem
Your AI Navigation works perfectly well when playing the level directly from PIE. But it doesn’t work when you Package it. It also doesn’t work when you start from a different level in PIE and then switch to that level containing AI. Tried various methods such as setting Runtime Generation to Dynamic or Force Rebuild on Load in Project Settings but still no results.
The Solution
Again, really simple and obvious. All you need to do is to Build the Path. For that, go to Build tab on the top and click on Build Path
This should fix the error for you. After building the path, you will notice that (for the first time), the RecastNavMeshDefault actor is finally asking to be saved (Now you know the problem. The navigation was building but never saving).