The only other current answer (by DT Cooper) is factually wrong. He's misunderstood the link he references and so the 30 - 40 years he's quotes has no baring on your question.
Orbits
Lets first understand how orbits work. If there are no perturbations (drag, solar pressure etc.,) then objects will stay in the orbit they start in forever. This is an idealised view of orbits as we're assuming there are no perturbations - in practice this never happens.
Perturbations
These are anything that can alter an orbit, alter doesn't have to mean reduce the altitude/cause reentry - some perturbations can act to have the opposite effect. The key perturbation in calculating how long an object stays in orbit depends on the orbits characteristics - lower orbits are overwhelmingly ruled by atmospheric drag, in higher orbits this can be negligible.
Orbit lifetime
How long an object stays in orbit can usually be simply put down to the drag on the object. Drag decreases exponentially with altitude, so a small increase in altitude results in a significantly longer orbit lifetime. Here's a good rough estimate:
Satellite Altitude Lifetime
200 km 1 day
300 km 1 month
400 km 1 year
500 km 10 years
700 km 100 years
900 km 1000 years
(Satellite orbit lifetimes)
You can see that an increase of a few hundred km in altitude results in roughly a 10 times increase in orbit lifetime. But as I said this is exponential.. so increasing beyond 900 km would give you more than a 10 times increase. For your question you've asked about objects lasting 1000's of years... so I'd suggest looking at altitude beyond 1,000 km.
How Drag Works
The above data is for satellites, but that's a very specific type of object. Drag is a force it's not a velocity - this means that the effect drag has is dependent on the mass of your object. This comes down to F = ma (or for us: a = F/m). But even this isn't a good enough level of detail because we need to know what the drag area (sometimes called cross sectional area, or wetted area) is for your object(s). Drag force is a function of the size of your object - specifically the area that your object takes up when moving through the fluid. If your object is long, thin and flies like a dart then it's drag area is very small, if it's more like a ball then it's drag area is much bigger. Objects at 1,000 km altitude with a very low mass but large drag area (eg, thin pieces of metal plate) could easily deorbit much more quickly than the graph above suggests - this is all due to the ratio of the drag area and the mass.
Some final thoughts
You've said it would be an extremely dense cloud at higher orbits. Have a think about how much mass that might be required for this dense cloud. If your objects are, say, 0.1 kg each at 1,000 km altitude in a range of +/- 1km and covering from pole to pole then you're talking about a volume of 1,368,000,000 km3 (that's 1.3 billion km3). If you want a 0.1 kg object every km3 (which isn't all that dense of a could) then you'd need 136,800,000 kg of mass in orbit - 136,800 metric tonnes. That is unimaginable, even for such a low density cloud. That's not to say a cloud of 1 object per km3 isn't prohibitive to launching more satellites - just be careful when you describe a dense cloud in orbit.