Obviously they exist. We saw them in the 22nd century working in parallel with Starfleet. We don't see them in the 24th century -- at least, not that we know of -- but then we've never seen the Andorians either, and I doubt they've gone extinct. Anyway, it's not all that hard to account for. The Dominion War would have had an EXTENSIVE ground theater on the worlds of contested systems (Chin'toka in particular) that we simply never saw because Starfleet ordinarily doesn't get involved in land action. That, probably, is where you'd be likely to find large groups of Andorians, Tellarites and Federation MACOs. Doubtful, since the only reason those Starfleet officers were there is because they needed to keep that particular sensor array and nobody had shown up to relieve them yet. AR-558 was apparently something of a backwater where no other ground combat was taking place except for that one little sensor array.