VPS And Smtp Mail Server

I recently purchased a VPS, to host all my domains and so I can start working on my sites. The problem is however that I have noticed that my provider does not allow individual smtp servers. Is this normal for a VPS? Is there a solution to the problem that I could suggest?

The problem is that the sender is added as host.myhostdomain.com and not smtp.mydomain.com, where mydomain.com is the domain that I want to create a website for and myhostdomain.com is the name of the server.

If the SMTP server is not the same as the domain name, then my email will land in all different junkmail folders, which is not really what I had in mind. It is no use trying to build up a user database if you cant communicate with them. How should I be able to sell services, if I cant send an e-mail to my customers?

I just dont know. I have to admit that I am a bit disappointed. It is not like I am paying a forture, but I am realistic. If one of them gets big I probably have to host them individually, but until I get more traffic this is a good solution.

My hosting provider runs Cpanel/WHM/Fantastico/XController, if that helps.

I have already tried to approach customer support about this issue, but the response was simply "With the PHP email issue, there really isn't a way to have it sent from some other address. It is technically coming from the hostname, so it will be labeled as such. In the php script, you can have it set to a different from
address, but the actual sender will be from the hostname."