Email troubleshooting can be divided into "sender" and "recipient" issues.
Since you are able to send to other people the Sending side is probably working fine. You need to investigate the Recipient side to locate the problem.
Looking at the logs is a good step and can tell you where your messages are getting to and where they are not.
Normal email flow goes like this:
You send from your email software to your server
Your server sends to their server
Their server sends to their email client
In this case you can see from the logs that their server seems to be
Messagelabs is an email filtering service that is now owned by Symantec. Message filtering services like this are used to remove all the spam and junk email before the messages are sent to the client software. This means that any messages blocked by messagelabs will not turn up in any spam or junk email folders in the client software. They will just disappear and the recipient will never see any sign of them. On rare occasions they may get a message saying that "a message from firstname.lastname@example.org has been blocked. Contact your IT dept to unblock it."
This sounds very similar to what has happened here. Technically you should get a bounce response from messagelabs like the guy in the link you posted but this is not guaranteed. They may just silently delete your message if they think it is spam.
Usually messagelabs will provide an interface for the IT department at their customer where blocked messages can be released. You can ask your contact at the company to check with their IT team for any blocked messages from your email address. At least you can if you have some other way of contacting them!
Other useful general troubleshooting steps:
If you didn't have access to the log files you can find out what the server should be for any domain by looking up the "MX records"
For example here: http://mxtoolbox.com/
The MX record is what an email server looks for to find out where they should send your email.
You can then initiate a manual connection to the server listed in the mx record to see if it is accepting email and what error messages you might get.
Use a telnet program like Putty: http://www.putty.org/
and telnet to the email server on port 25. Some of the commands you will need are listed here: http://www.yuki-onna.co.uk/email/smtp.html
So now you can connect to their mail server and send an email using your email address as the "From" address and see how the server responds directly.
Any email error codes that are returned can be looked up in google or here: http://www.serversmtp.com/en/smtp-error
Once you have checked that you can connect to the server it may tell you why your email is being rejected as spam or for some other reason, but the reason may not be easy to decipher. At this stage I would suggest you ask the messagelabs customer to contact their support number with the error codes (or lack of them) that you received from their server. Since you are not a customer of messagelabs you can't log a problem or ask messagelabs to check the settings on their customer's account. Their customer will have to ask that themselves. This would be similar for any other mail filtering provider.
Hopefully the error code would point you to a particular problem, like your server being listed on a block list or lacking a SPF record and you can fix that yourself because dealing with a mail filtering provider at third hand is never fun. The last problem I had like this took over three months to resolve before the fault was located and messagelabs fixed it.
I will defer to the answer by kubanczyk for details on SPF and DKIM settings because they seem to be much more knowledgeable than I am!
Speaking as someone who reads other people's email as part of my job, it really, really, REALLY depends on what your mail environment looks like.
The short answer is:
Exchange with Outlook
The system does track the Last Logged In user for a mailbox, but that attribute isn't easily viewable without the Admin Tools. The Admin Tools that would be used to view the same mailbox.
Generic IMAP4 + Thunderbird
Unless the mail administrators have taken the effor to publish your last login list somewhere, the only way you'll know is if mails get their read/unread status changes, or mail moves mysteriously.
Google does in fact publish the last few IP addresses that logged into the account. Its at the bottom of the page. Check that, and if you find addresses you don't know about, it's a good sign that something strange is going on.
Generic Corporate email systems, not just Exchange
All incoming mail is copied to a specific address. Or perhaps only people of interest. Since this copy happens while the mail is still just a text-file in a mail-spool somewhere, you'll never know. This kind of setup is very, very common in E-mail Archiving setups.
Steps to take
Changing your password is a good first step if the mail is being monitored by an actual login. It won't help if the mail is being copied out of a mail-spool before it actually gets into your mailbox; there is exceedingly little you can do about that scenario. If it happens again after your password has been changed, then something else is going on, and it's time to take it up with your mail administrator.