It was around the release of patch version 1.5 that we realized that these problems would magically disappear if we converted our .esp files into .esms.
When patch 1.6 came out, I'd personally thought that the problem was resolved with it. I know now that I had not tested completely enough and I was mistaken in that.
So recently (its patch 1.7 right now), a post got my attention here on the board, and I went in and tested thoroughly, and discovered the problem to still exist.
So now I have done a bunch more testing. I first tested the 1.7 executable and made a video showing how I could get the problem to happen reliably with my cell.
Then I uninstalled Fallout 3, removed all mods, and reinstalled it from my disk (EU english version). Then, for testing, the only mod I loaded was my mod which contained the custom interior cell (aaphalanxbunkerinterior) and it also contains follower changes (its Phalanx-MainFollowerModule.esp).
I ran my test within the completely unpatched game. The symptoms were identical.
Patched it to version 1.4. The symptoms were identical.
Patched it to version 1.5. The symptoms were identical.
Patched it to version 1.6. The symptoms were identical.
After finishing patching back up to version 1.7, I converted my .esp into an .esm using FO3edit. The symptoms were gone.
A video showing my demonstration of the problem (using the 1.7 .exe) is here: http://www.youtube.com/watch?v=0d2rt1_qUMY . It's 7.5 minutes long. the video was recorded with more mods loaded than were in my tests with 1.0, 1.4, 1.5, and 1.6 but it doesn't matter, the symptoms did not change based upon whether or not I had my regular set of mods loaded.
I remain hopeful that this problem may be fixed in the future, and we can have .esp files that work right with navmesh in new interior cells.
If this problem still exists when I'm ready to include a new interior area in my mod, my personal plan of action is to cause all new interior cells for my mod to exist as an.esm file with the correct .esm file extension (not a stealth .esm). Then, my main .esp file will carry that .esm as a master. It may be necessary to script the doors in and out of such a cell to enable followers to enter and exit reliably, if my recent experience with Broken Steel's citadel door carries over into this situation.
I'll link the video here when it's done at youtube, and I'll throw a bug report into their software forum after that I guess :/