Möglichkeit a):
Mailversand erfolgt über eigenen "lokalen" Mailserver via der PHP Funktion mail(). Diese ruft dann ein Programm auf, welches in der PHP-Konfig angegeben ist (meist sendmail unter Linux, was dann alles weitere erledigt).

Möglichkeit b):
Auf einen anderen Server (könnte theoretisch auch der eigene sein) zugreifen/Verbidnung aufbauen und über dessen SMTP-Software die Mails verschicken.
Hier nutzt man sowas wie fsockopen(), anstatt mail(), und für den Versand wird ein anderer Server genutzt, beim eigenen macht das wenig Sinn.
Wie man das umbauen könnte, gibts afaik hier irgendwo nen Thread, find ich grad nicht.

Interessant wär natürlich schon, was da jetzt genau los war, normalerweise müsste/sollte dir der Hostzer ja die Logs zukommen lassen (wäre auch in gewsserweise ein Qualitätsmerkmal), dann könnte man sehen, obs richtige Spammails waren, oder doch nur Paidmails (dass kann der Hoster denke ich kaum unterscheiden, wenn er Klammlose Seiten nichtkennt)