How do I change the site mail address?
Based on the comments, and narrowing down the problem to the Rules module itself, or its integration with the mail system:


Tokens work elsewhere
Tokens within the body of the message work but not the from field
No templates are used
Core mail as well as third-party mail are affected
Clearing the cache, including the rules one, had no effect


It would appear to be a bug in the Rules module or the mail delivery part of it. I would suggest adding an issue to the Rules issue queue and see if they can further explore options for correcting the problem.