Minecraft – Nether portals exiting into a different location

This is how it works:

Every time you enter a portal, the game looks for an exit portal inside +/-128 blocks square (y is irrelevant). If you enter a portal at x=100, y=60, z=200 in the overworld, this corresponds to x=12, y=60, z=25 in the Nether. The game scans a square from (x=-116, z=103) to (x=140, z=153), for all y values from 0 to 128. The closest portal in that space is where you appear. If there is no portal in that area, one will be created in a suitable place. Since there is a chance the x=12, y=60, z=25 will be obstructed, the game will search for an open space in that +/-128 blocks square. If such space is found nearby, all will be good, the new portal will lead back to the same one in the overworld.

Note that the game will only scan within the map height. That means that if you place a portal above the nether ceiling, it won't be found, and the game will create a new one for you.

However, sometimes the game will put the Nether portal far from the starting point, if it can't find other suitable place. Let's say it puts the Nether portal at x=80, y=60, z=110 (this is still in the +/-128 bounding box). When you enter that portal the game will search the corresponding space in the overworld: starting from x=640, z=880, it will search the +/-128 blocks - from x=512, z=752 to x=768, z=1008. As you may notice, the original overworld portal is well outside this box. So the game will create a new portal in the overworld. This is what is happening in your world.

To fix that, write down the coordinates of the portal in the overworld (use F3 to get them) and divide them by 8. Enter the Nether, go to the calculated coordinates and create a portal from the Nether. You don't have to be exact, as long as you are within 16 blocks from the calculated coordinates (you need to match only x and z, y is irrelevant). Then the game should find the original overworld portal. Or: Move the overworld portal using the above logic.

In described situation, there is no way to make the two portals lead to each other without moving either of them. I'd move the nether portal and if the new position is outside of the fortress, I'd build a short safe walkway to the fortress.

Here is a crude drawing of the process:

The distance that your new portal needs to be away from the old one isn't terribly large, only 128 blocks, but it's measured in terms of the destination world; every block in the Nether is worth eight in the overworld, meaning you'll need to move around 1024 blocks or so away to keep a new portal from joining the one that already exists in the Nether.

I say "around 1024 blocks or so", because the existing portal on the nether side may already be some distance away from the location that would best match up with the existing Overworld portal.

There are, however, a few other options. You could try building a bridge across the lava on the Nether side. Painful and awkward, but once across, you could build a new Nether portal on that end, destroy the Nether-side one that exists (just punching it to turn it off should suffice), and hope that the new Nether-side portal successfully connects to your existing one. Alternatively, you might be able to make a suicide run through the portal, destroy the island so it's no longer a valid spot (and also destroy the portal on that side, too), then once you die and respawn on the Overworld side, a quick trip through should trigger the creation of a whole new Nether-side portal, which might not be in such a poor location.