I am trying to send email from my webserver to email server via phpmail.

The webserver has a random hostname e,g abc.examplehost.net

The problem is that postfix on my email server rejects to receive these emails saying;

Domain not found 450

Considering I don't want to change hostname of my webserver. How can I make the emailserver let these emails go through without much compromise on security.

I'll truly appreciate some help here.

Check your Postfix configuration, in particular the smtpd_sender_restrictions setting. Does it include one (or both) of the reject_unknown_sender_domain or reject_unverified_sender options?