Even satellites that are not in those 22,300 mile high orbits will stay
in space for a very long time if otherwise left alone.

Vanguard 1 does indeed have about 1.5 centuries to go in LEO.
There was a recent article on talks about recovering it for the
Smithsonian NASM around the 50th anniversary of its launch.

The LAGEOS 1 satellite, which was placed into a 5,900 kilometer
high orbit, will last for 8 million years before coming down. This
is why Carl Sagan designed a specially made plaque depicting how
the planet's continents will drift over time (the satellite was designed
to help measure continental drift) so that future finders will know its
purpose and when it was made and sent into space.

You can see the plaque here:

One of the images on the Voyager Record was a modified version
of the LAGEOS plaque. Those probes should last at least 1 billion
years in interstellar space.

Some details are here:

http://www.bigear.org/CSMO/HTML/CS07/cs07all.htm