Since migrating to Lion, I’ve noticed several of my Mail rules fail to run. I have a number of rules that tag and move incoming messages. Rather than waste time trying to figure out why the rules do not run properly, I just setup a scheduled Keyboard Maestro macro that runs the rules for me. So far, this seems to solve the problem.
Edit: Take out the "Activate Mail" step unless you want to drive yourself crazy.