Smtp bez webhostingu?

Dobrý den, máme u vás doménu mestolaznebelohrad.cz, webhosting nám zajišťuje jiná společnost. Chci po nich, aby mi z aplikace odcházely maily pod @mestolaznebelohrad.cz. Oni mi tvrdí, že musím mít SMTP server (a ještě nějak nespecifikovaně zajištěný (nějakým záznamem u domény), aby nebyly maily vyhodnocované jako spam). Rád bych se zeptal, jestli je možné získat SMTP server bez webhostingu a budete komunikovat s jiným serverem? V opačném případě bych potřeboval webhosting – mám u objednávky odškrtnout „nastavit DNS“?

Děkuji.