Unless I want a copy of Crazy Taxi, Code Veronica, or one of the 2K sports games, I pretty much have to resort to eBay. The local shops used to have a pretty decent selection, but it's dropped hard. At least they still carry new Naki VGA boxes for $10.
Last time I bought a Dreamcast game at a place like EB, I had to take it back for a swap. They apparently weren't looking at scratches all that well. Strange thing is that not only was it a copy of Street Fighter III: Third Strike that I was taking back due to skipping from scratches, but they also had a copy to give me in return. Of course, that was about 3-4 years back, but even then it was hard to find.