A good place to start would be to check that your port 25 is open to the world, if your at the same public ip address as your server you can use the custom port test at http://www.whatsmyip.org/ports/
If your outside of your local network you could try and telnet into port 25 at our servers public ip address, the command you need for this is simply 'telnet yourpublicIP 25'
You should get a result like '220 server.domain.com ESMTP Postfix ' if all goes well. If you get the result connection refused then you may either have your firewall/router misconfigured or your isp maybe blocking port 25.
As far as the DNS goes you should only need entries at 123-reg and not your server, unless you are running secondary DNS on it for the domain.
In the 123-reg DNS management section you should add a new A record with the following details, using the terms 123-reg use, the Name should be 'mail' (without the quotes) the Type is A and the Content is your public IP address.
Then you need to add the MX record, this should be 'mail.yourdomain.com.' (without quotes, with full stop) and set the priority to 10.
It looks from above that you still have some MX entries for the 123-reg mail servers, this shouldn't be necessary unless maybe you are using their mail forwarding service?
Hope it helps.