I dunno - I've got around ~20 gigs of music, only 3 (songs, not gigs) were purchased through the iTMS, and genius works pretty good for me most of the time. I would guess though, that it's more likely to work with songs available on the iTMS.
Anyhew, it's a great feature - when I heard about it, I thought 'meh', but after using it - it's really fantastic. It's nice going to work in the morning (long commute) and rarely ever having to hit 'skip' because I've come across something on my iPod that I'm not really in the mood to listen to...