Many countries have changed it's political boundaries in the course of history. Some gained and some lost territories which heavily reflected philately and will be reflecting in future as long as stamps will exist.
Today I'm posting few stamps with a postmark of lost territories of any country, I personally think it is very interesting.

German stamp with a postmark of Danzig, today Gdansk, Poland.

Hungarian stamp with a postmark of Fiume, today Rijeka, Croatia.
I'm very aware that both Danzig and Fiume issued their own stamps but it does not fall into the category of "lost territories" since from the beginning to end of the issue of the stamps the Free city of Danzig, there has been no territorial gain or loss, and so does Fiume as well. So only the stamps of the countries that have known a "territorial change" can be qualified as "lost territories". I hope you understand what I'm writing.
I would like to see what you have and will appreciate if you can post it here! Most of those territorial changes are not mentioned neither in Scott nor Michel so it will require a wide knowledge of history and geography.
Few more examples I have

Kharbin Voksal (railway station) on Russian stamp, today China.

Kassa, Hungary, today Kosice, Slovakia.