How do you keep a workflow rule from executing multiple times?

This week, I was told that people had received emails due to a workflow rule that was set with the following Rule Criteria:

     (Contact: Professional Reference Name NOT EQUAL TO null) AND (Contact: Professional Reference Email NOT EQUAL TO null)

The Evaluation Criteria were set to the following:

     Evaluate the rule when a record is created, and any time it’s edited to subsequently meet criteria

The problem was that the record had been edited, but I am almost certain it already had these fields set with values.

Is there something I'm missing as to why the rule would get evaluated again?

I noticed that the wording of the evaluation criteria has changed now from what it used to be, as of Winter '13 release. The actual functionality is still the same, though, right?

I've edited the Rule Criteria to now be  as follows, to see if more stringent criteria will help:

    (Contact: Professional Reference NameNOT EQUAL TOnull) AND (Contact: Professional Reference EmailNOT EQUAL TOnull) AND (Contact: CVC Intern StatusEQUALS4. Screened Applicant)

However, there are cases in which Contact records with CVC Intern Status = "4. Screened Applicant" could get saved again, so I would like to be sure that the Evaluation Criteria I have set would prevent the message from being sent more than once.

What would happen under my current Evaluation Criteria if a record was changed to have a different CVC Intern Status and then was set back to "4. Screened Applicant". Would the rule be evaluated, and thus the email sent again? I don't want that to happen. 

Is there an option for Evaluation Criteria so that it only is evaluated the first time the record satisfies the criteria and then never again? I think there used to have been one, and that is the behavior I want, in this circumstance and for several other rules as well.