Your world must be older than you remember. If it was created back in the 1.8 series then strongholds would not necessarily be in the same place (and there were fewer of them). Testing that seed in 1.8.9 yields the same large mineshaft complex, but no stronghold. However, that also means you have been in the that area previously to generate the chunks without the stronghold (new chunks follow current version generation).
I looked and 1.9 was released in February 2016. This world was created perhaps 6 months ago. I never played Minecraft before that.
Wow, we definitely have a mystery! Those coordinates do not take me to the staircase or the portal room. Check out these screen shots. On one of the screenshots, you can see the seed - so I did copy it correctly.
Any thoughts? I'm in Australia, but why in the world would that matter?
Here is the last photo showing the coordinates where you found the portal room.
Wow, that stronghold is quite the mess, but an interesting one!
The spiral staircase, which is generally considered to be the entrance to the stronghold, is under an island at -1261 62 708 (dig down from there). If you'd like the coordinates of the portal room, just ask.
Could you recheck those coordinates of -1261, 708? I dug straight down and did not find the spiral staircase. It also didn't seem to be on the island. And yes, I would love the coordinates of the portal room, if you could include the level, I would greatly appreciate it.
I was searching for the closest stronghold by using the eye of enders. I found the spot where the eye wouldn't go anywhere, just down to the ground. I dug there and ended up hitting bedrock. No stronghold. So I dug out a large horizontal area at about level 20 and threw another eye of ender, and it went to the same spot that I had mined down to the bedrock.
What happened? I really want to find a stronghold, but even when I travelled far away and tried again, the eye of enders took me back to the same spot.
Any advice or insight would be greatly appreciated!