I am ALL over this! Finally, someone I can help! I'm not sure I 100% understand exactly what your problem is, but it SOUNDS familiar.
Sticking the trigger_changelevel in an inaccessible area. Yes, you got that right. You need a trigger in both maps, though. The truth is, you're probably not spawning in the dead center or origin of the map, but rather in the exact coordinates that you were at when you hit the first changelevel trigger. When you hit the trigger in the first map, or map1, your coordinates are "recorded" by the engine on the X, Y and Z axes. You will spawn in that same exact spot in the next map, or map2.
So, to reiterate; Goldsource doesn't care if you have a floor and walls there to receive the player or not. It will spit you out at the exact same grid coordinates that you were at when you hit the trigger in map1. Even if that means placing you in the void in map2.
Or you did something wrong with the landmarks. They need to have the same name in both levels.
The BEST thing to do is place your trigger changelevel and landmark in map1, compile it, then copy map1.rmf, rename it to map2. Open up map2, move the trigger_changelevel to a different spot,(in this case, out of player range)and edit the parameters to enable the trigger to go back to map1...even if it is out of reach. Then delete the old geometry and continue on mapping the rest of map2.
Fun Tip: Trigger_changelevels can be targeted by trigger_once and multi_managers.
(EDIT) Just re-read your post. Yeah, you need landmarks and trigger in BOTH levels, named appropriately, or you will default to the origin of the map and be trapped in purgatory forever. Just stick that trigger_changelevel way out of reach and flag it to "Use only" for extra security. It STILL needs to have the proper information - the same that it would have if it was a two-way change.