Yes, the landmark has to be in the same place in both maps. It doesn't matter where in the map it is, but the area where the level change goes on is usually the only consistent thing between the two maps, so people put them there.
Also, if you have the trigger_changelevels in the same position in both maps, it'll probably go into some kind of infinite level change loop, although I'm not sure (I've never tried that myself.) It's a good practice to keep plenty of room between the two trigger_changelevels, so the player doesn't skip right back to the previous map if they step backwards after the level change.
And does the changelevel FROM one room still have to exist in the other if the swap is one way?
Even if the level change only goes one way, you still have to have a trigger_changelevel that leads to the previous map, yes. Put it in some secluded spot in the map, or just check the "USE only" flag.