The non existent subdomains on Google have increased from 6 to 80.
Yes, there are several subdomains as described by you in search results. While these will not affect your SEO/ ranking, it is quite intriguing. Ordinary search tools do not show any such subdomains. But, when I tried to translate one of the pages today using Google translate, it showed '403 Forbidden'.
However, though your host also do not find any thing wrong, I doubt, it can be a case of ADWARE or some type of hacking.
Anyway, did you try deactivating all plugins and revert to Twenty Twelve theme to check if the nonexistent URLs are output by the theme/ plugins?
Do you have backups of your site, of a date before you noticed the nonexistent URLs?