Have you tried to SMTP to that server on port 25? This would indicate if the server is listening (as it should) on port 25.
Other possibilities (some of these I have experienced in BES2.2 versions...may not be the same here)..
1. Does your contact list on the device have two addresses for the same contact an smtp address and notes address? I have found senders with more than one address for a receipient received mail router errors. I haven't seen this in BES4.0 as yet though.
2. Check your router service logs for the BEs server and see if there are any address resolution errors. Some receiving MX servers do reverse lookups on the sender and if unable to resolve, simply drop the connection.
Have you been able to send to this receipient from your device before?
A good tool to check smtp connections/DNS issues is SMTPDiag...this can be found on Microsoft's site. Place the *.exe in any designated directory and run the tool from that dir at a comman prompt. It's fairly intuitive to figure out.