There used to be an Orange Free State landlocked in South Africa.
Nope, doesn’t qualify. During the period it was an independent republic, it bordered the Transvaal, which in turn bordered Mozambique (and also Southern Rhodesia and Nyasaland, now Zimbabwe and Malawi… but they were British, same as South Africa, at the time).
I think a couple of the “Bantustans” under the old apartheid South Africa government were surrounded by South Africa – but nobody recognized them as independent except South Africa.
I feel the Northwest Angle deserves some mention here, so the bodies of water ought to start with Lake of the Woods. (For those who don’t know, the Northwest Angle is a bit of the US inaccessible by land without crossing the border, but not an island. It’s connected by land to Manitoba, but not Ontario).
There’s also the term Princely State, which was used in British India for non-sovereign regions that had limited autonomy.
edit : Some of the Princely States were also landlocked in this way (e.g. Kashmir).
Kashmir actually shares a border with China, so even counting the present territory of Pakistan and India as being one country under the Raj, it wouldn’t be landlocked in the same way that the Vatican or Lesotho are. However, along those lines, had Hyderabad become independent, it would have been completely surrounded by India.
Edit: Kashmir also has a small border with Afghanistan.