Couple other little tidbits -

Spies can also gain valor if they reveal a secret vice for an enemy, or if they successfully frame one of your own generals for treason. A spy can also gain valor if there is a rebellion in the foriegn province he is sitting in.

Spies, assassins and emmisaries who are "counterspying" - ie sitting in one of your provinces doing nothing - may gain a star if they catch a forigen spy. Doesn't happen to me very often because I build border forts.

An assassin may gain more than one star if they kill a very important target. Take out a king with your assassin and he may gain two stars instead of one.

HTH