National Geographic keeps impressing me. In addition to having a great holiday gifts catalog, they have a treasure trove of international music videos on their website. The site includes Brazilian, flamenco (check out Estrella Morente's Volver), Arabic pop, and even "Garifuna music."
Here is K'naan's "Soobax."