Thrift stores!!! Plus they are totally ok re: you being in the "wrong department". While there yesterday I shopped in women's, men's, and kid's. The ones I go to have generic dressing rooms.
If you go to a really upper crust neighborhood, it will work better. In Chicago, I used to go to one run by the Junior League. I swear they threw out stuff after they bought it as some had original tags on it.
--Jay Jay