The reason why only the southern and eastern edges need to be repopulated is due to the offset to the south and east, which will overlap with chunks generated to the east and south - or the chunks which already exist along the western and northern sides, which will be populated when the chunks to their west/north generate, and is why you don't see any unpopulated chunks along those sides in a normal world ("unpopulated" actually marks a flag within each chunk which tells it to populate if the chunks to the south and east are present).
You have to deselect the area then only select the area that you want to repop; you definitely do not want to repop areas you've built in, especially if you use blocks like stone (including the variants) as ores and water/lava springs may generate in them, and the game will spawn passive mobs on top of your structures, even if there isn't any grass (only normal mob spawning depends on grass and light levels).
That has to do with the way the game populates chunks with features, as explained here (under "The Cause"), which is done so that features can cross chunk boundaries without loading more chunks (as the thread topic suggests this is very bad for performance and can even crash the game).
As for NBTExplorer, "msi" refers to a Windows installer and will set it up like a normal program with a folder in program Files, start menu ions, and all that; you may just want the "zip", which can be extracted to any folder and ran from there (it is pretty much a standalone program, it may require some .NET libraries but you probably already have them installed).
You can either use NBTExplorer to edit the seed in level.dat (saved under "RandomSeed"; note that this must be a number) and delete chunks as you did before or use MCEdit to copy your base to a new world (select the area and export as a schematic, then import into the new world, making sure that it is correctly aligned so terrain matches, and that the schematic does not extend outside of generated chunks). The former would be much easier to do since you'll lose everything in your inventory (including Ender chest) if you copy everything to a new world. However, if you delete chunks you also want to delete all the structure files (Mineshaft.dat, Village.dat, etc) inside the data folder so they regenerate correctly (otherwise they will have no mobs, chests, or spawners, and you may have extra structures which were recorded with a different seed generate), and make sure that the boundary between old and new chunks is mostly underwater or in biomes like plains or desert to minimize artifacts like cut-off trees (you'll also want to select the chunks along the southern and eastern edges and click on "repopulate", so it looks like this, to make sure that the game correctly populates new chunks next to them).
Can you post a screenshot of these "vertical walls"? Do they look like this?
Or like this?
If you see the first example it is because you did not actually delete the chunks, only the blocks within them, which will turn them into empty chunks filled with only air. Otherwise, if the "walls" are limited to differences in terrain height and biomes are different on either side then it is due to a different seed and the original seed is likely forever lost unless you remembered it or wrote it down, but it sounds like you were able to recreate the world (did you use the "recreate" button or did you make a new world with a seed that you remembered or wrote down? If the latter, the original world may have a different seed if you recovered it by replacing level.dat with a different file, which will change the seed unless you used the same one).