In the same vein, MessageLabs blocking works on the envelope (smtp) sender, not the From: header. If the mail you are receiving has a different email address in the smtp sender to the one in the From header, you will need to block that.
You can find out what the envelope sender is by looking at the headers to find the X-Env-Sender header which MessageLabs inserts.
The other thing you could do if this is a genuine company sending you mail rather than a botnet is block their IP address.