La verdad es que Google te ofrece 20.000 canciones para almacenar en la nube y la mayor de las veces no se usan. Puedes elegir entre reproducir las canciones solo con Wifi o también con 3G y entre máxima o calidad reducida.
Creo que si combinas Wifi con máxima calidad y Tarifa con calidad inferior no tendrás problema ninguno. Además las canciones se almacenan en caché y a la siguiente reproducción no hay que esperar.
En cuanto a las canciones de origen "dudoso". Yo he subido discos de música ripeados de mis discos originales y otros descargados de Internet y 0 problemas.