Hast du denn auch die korrekte Shopbetreiber E-Mail hinterlegt? (Einstellungen -> Grundeinstellungen -> Shopeinstellungen -> Stammdaten)
Theme oder Plugin halte ich erstmal für unwahrscheinlich, sollte aber auch mal geprüft werden. Ansonsten wirklich den Hoster oder Mail Provider ins Boot holen.
LG Andre