There's a place in Mesa called Bookmans. (It's on Country Club and Southern I believe. In the same place as the Arby's) They sell old books, CD's and have a videogame section too. Last time I checked them out, they had a few used Dreamcasts and controllers. Their DC software selection wasn't all that great, but at least they had something.
There's also another place on Alma School and University behind a Kentucky Fried Chicken. I can't remember the name of the place (someone in Bookmans actually told me about them) but they've got loads of stuff there too. It doesn't look like much from the outside but the people who work there are pretty nice.
I'll try and get the name for you...