Add Category by Domain Rule Failure

Can anyone shed some light on this for me please?

I have set up a rule that says: If "domain.com" is found in senders email
address then assign "Category X" to it.

We are using MS Exchange 2003 and I am on Outlook 2007, which means that it
says that this is a client only rule which will only run with Outlook open
(that's fine).

I ran the rule for current emails in the inbox and it worked but I then
received a new email from the same person which did not get categorised. I
tried running the rule manally but it didn't do it either. (The email it was
sent from is exactly the same as previously)

Also, I seem to have a problem where internal emails are sent, I can't get
it to reckognise the domain at all.

Any help would be appreciated.
--
Tim Waters