Minecraft – What makes a Wither Skeleton spawn

According to the decompiled sources, Minecraft stores the location and volume of generated structures such as villages and Nether fortresses in a separate data structure to the actual blocks that we see in the game. Part of this data structure is a list of mobs that can spawn in that volume of blocks.

Each Structure is composed of Structure Pieces, and each Structure Piece has its own bounding box and mob list. A single Piece can spawn multiple other Pieces adjacently if the type of structure allows it, so one Nether bridge can trigger the placement of another bridge span, or a Blaze spawn platform, or a room, or a tower, etcetera. This is what creates the sprawl of "one" Nether fortress – what we think of as a Nether fortress is really a bunch of independent Structure Pieces that happen to be side-by-side. You can see that in the second video of BlaXpirit's answer, where each red-lined box is a different Structure Piece placed by the structure generator. Each of those bounding boxes are sized to fully encompass all blocks placed by that one Piece's block generator.

For the purpose of spawning Wither Skeletons, all locations in a Nether fortress can spawn them, assuming that spot is a valid spawn location for a mob pack in the first place. It's not "some locations" at all, but every single block, including air, that is within any Nether Fortress Structure Piece bounding box. The code works like this:

1. The spawning algorithm selects a single X,Y,Z coordinate to check.
2. If it's a valid spawn location according to light levels and solidity, it will spawn a mob there.
3. To figure out what mob to spawn, it queries the world data structure to find out if that coordinate is inside a Structure.
4. The world data structure finds all Structures that claim blocks in that chunk and then ask them if the coordinate is within one of their bounding boxes. (Structure bounding boxes don't overlap.)
5. We'll say the spot is confirmed to be inside a Nether fortress Structure Piece bounding box. The bounding box is a rectangular volume that encompasses the Piece. Nether fortress pieces are usually made of straight sections of blocks, making it unlikely for the bounding box to contain much outside the walls, but it's possible. This means that the spawn coordinate can actually be outside the walls of the fortress in unusual block layouts, especially if the fortress has been changed.
6. The spawning algorithm then asks the Structure Piece for its mob list. Nether fortress Pieces' list is Blazes, Magma Cubes, Skeletons, and Zombie Pigmen. We'll say it picks Skeleton.
7. The spawning algorithm places a mob pack on that coordinate. Because packs spawn multiple individual mobs in a radius from the pack coordinate, this can actually place the mob outside of the walls of a fortress, if there is valid ground there.
8. Placing a Skeleton in the Nether triggers a check: 80% of the time it will be a Wither Skeleton, otherwise a normal Skeleton.

Consequently, Wither Skeletons can spawn everywhere inside of a Nether fortress that is a legal spawn location for mobs, and can sometimes spawn on blocks slightly outside of the volume claimed by the Nether fortress' Pieces. The region is fixed and unchangeable after the fortress is generated. One implication is that you could maximise Wither Skeleton spawning by adding more layers of blocks within the Piece's volume, to convert more air spaces into legal spawning pads.

Based on this table of status effects from the wiki, a potion of regeneration or a golden apple will give you regeneration for a short time, which should heal hearts over time faster than you lose them from the wither effect (1 gained every 25 ticks from the regeneration versus 1 lost every 40 ticks from the withering).

Also, drinking a bucket of milk can remove all status effects.