OK, after some more digging, I actually found the REAL problem: this "extra NPC space" issue only occurs with NPCs that are moving up or left. The reason for this is that within NPC data, the game keeps track of NPC coordinates in two ways: tile coordinates and pixel coordinates, where each tile is 16x16 pixels. There's an update function that gets called to update the NPC's tile coordinates based on its pixel coordinates, but it always rounds down, so when my "NPC space refresh" function is called with NPCs that are moving up or left, the coordinates end up being one space off in that direction. I know how to fix this, but first I want someone to confirm or deny this: apart from the World Maps which are 256x256 tiles, are there any maps in the game that are wider or taller than 128 tiles? I think the answer is no.
We have EVEN MORE themes now, but some old ones are gone...