The NX01 lasted 100 years in "E2". Discovery lasts 1000 as of "Calypso". I doubt all those Excelsiors, Oberths and Mirandas in TNG/DS9 are new builds, either.
Based on the registry number of certain Excelsior class, like Valley Forge at Chintoka, being NCC-43305, it was a new-er build, as well as the Excelsior Variant 2 USS Lakota being NCC-42768, which would put them between the Ambassador class of the 2330's and 2340's and the Galaxy class of the 2350's. So they were being new-built until at least 2350.