I'm assuming this question is about D7 ...
Step 1 - Flag published revisions
Use the Flag module to flag Workbench content whenever a published revision gets created. The flag you'd want to use is a global flag. To actually flag such content, use the Rules module.
Step 2 - Check if flagged
Adapt your existing Rule(s) (for advanced Workbench notifications) to take into account if your content has yes or no been flagged. To do so, you have a choice:
- Split your current Rules Action (for those notifications) in 2 Rules Components (in which you can use Rules Condition to check the flag).
- Use the Conditional Rules module so that you can include the required Rules Condition(s), to check the status of the flag, within the Rules Actions of your existing rule.