Not exactly sure if this is a native bug since I did use a third party program (MCC Toolchest: http://mcctoolchest.com/Download) regardless, this is what happened:

1. Have a world created pre 1.16, with loaded Nether Dimension.
2. The loaded Nether Dimension has (obviously) created a Nether Portal at some x1,y1,z1 upon entering from the Overworld.
3. 1.16 comes out. I use MCC Toolchest to delete the Nether dimension.
4.  Go back in the world and enter the Nether using the same portal I did before 1.16
5. Now in the updated Nether, the land is clear from any player alteration... but the Nether Portal is not there.
6. I kill myself to return to Overworld.
7. I create a new Nether Portal, adjacent to the portal in step 4. I spawn in the same Nether location as step 5, still no portal in the Nether side.
8. I kill myself again to return to the Overworld.
9. Now I go a thousand blocks away from the original Nether Portal, build a new portal in the Overworld and enter.
10. I spawn in the Nether at a different, brand new location from steps 5/7. THE PORTAL SPAWNS IN THE NETHER THIS TIME.

So it appears that despite the fact I deleted the Nether dimension in my world for the new update, it appears that the game still thinks there is a Nether Portal in the Nether that is linked to my original Portal in the Overworld. Again, I do realize this operation involves a third party program, but I wanted to bring this issue in case there is more to this.