Type it in greek. Else use well known artists & browse those hosts. Also see How to find music. However when looking for rarer stuff, I tend to use general search & vary my search terms. You can search by artist or/& album or/& song title. Perhaps even year or live, etc. eg: artist - title, or artist - album, or artist - 1992 etc.

But I guess it also depends on how many other people are sharing greek music. And by what language or key id3 tags they use.