Actually, it's much less that you'd think. In the earlier mixes, up to half of the songlist was Toshiba-EMI licences, but it's got lower and lower since. For example, in DDR SuperNOVA 1, there were 301 songs. Only about 25 of these are actually licenced. Actually, I might be able to provide a list of what songs can be remixed, but it'd be a long one. Also, there are about 60% licences in an XBox DDR, so they probably should be avoided.
EDIT: And here we are. Well, I said it was long. I've removed all licences, as well as remixes of classical music, and songs that were originally on another album before making it into DDR. Yeah, this is only the DDR list (all songs that can be done that are in DDR, regardless of if they were on another Bemani first). The extra ones for Pop'n Music, beatmania, etc. would be even longer, so...
http://www.megaupload.com/?d=LOFVO99Z