So your firewall is blocking outgoing port 25.
There is probably a rule in the firewall that only permissted outgoing SMTP from the IP of the baracuda.
Fix the firewall so you can telnet to port 25 on either
a) smart host
b) direct SMTP to destination SMTP servers.
The issue here is not exchange it is the firewall (your firewall). Fix the firewall and exchange will come good after that.