I don't know what cards you are playing with typically, but this is not my experience with gardens. With some sets of cards, this will be the dominant strategy (Ironworks+Gardens is a beast; workshop+gardens is fairly good as well), but with others (no "gain a card" cards), not really. You don't need a sparse deck or trash-heavy cards to counter gardens. A gardens player will tend to have way less purchasing power and a lot more clutter than a non-gardens player. If you can make it so that they don't get to the 40 card mark, you have some of the gardens, and you focus on duchies or provinces quickly, you should be able to win.
Now that you have prosperity, there is one killer counter to most garden sets available: Bishop. http://dominionstrategy.com/2011/02/23/counter-of-the-day-10-bishop-v-gardens/
There's some additional tips for countering it here, though the article mostly focuses on when gardens works: http://dominionstrategy.com/2010/12/16/dominion-gardens/
I've only played with prosperity once so I'll have to see how that affects things (it was a goon dominated game). You are right that if there are no gain cards it's harder to make gardens work but they just seem to be so common that it is a rare game where gardens exist and don't make sense.
Last edited: