If I purchase your paid email service can I overcome the issue on port 25 outgoing traffic?
Is any static ip required at my side?

You can use the Email Store/Forward service to host your email server on a port other than port 25. Your emails will go to Dynu's mail servers and then get forwarded to your email server. You don't need a static IP on your end because you can use a free dynamic DNS host to get your emails forwarded to your mail server.

To send outbound emails, you can use the SMTP Outbound Relay service and you don't need to have a static IP to use that.