You're defending a system that's barely a century old. The universal passport system was created in 1920 after WWI. Before that, movement was far more fluid - even the United States didn't require passports for international travel until 1941, except briefly during the Civil War and WWI. The U.S. Border Patrol wasn't even established until 1924.
The current system of border controls was introduced during WWI by European governments to control 'subversives' and prevent people with useful skills from leaving. When peace came, governments simply kept these wartime restrictions.
Your medieval examples actually prove my point - they were just letters of safe passage or tax receipts, not universal requirements for movement. The standardized global passport system is barely a hundred years old, yet you're treating it like ancient wisdom.
Respectfully, what you're calling 'natural' is actually just modern state control that would have been alien to most of human history. You're mistaking a century-old wartime innovation for timeless human behavior.