Best way is to use Smart Groups for your scope in the Self Service policy.
For example, if you had a SS policy to install Firefox, make a Smart Group for Macs that don't have Firefox already installed, or you can get more granular and look for Macs that either a) don't have Firefox already or b) don't have the specific version you're deploying with your Self Service policy. Use either Application title > Has > Firefox or look for a package receipt, if its something that was installed with a package of some kind.
The same general principal can be used for hundreds of different scenarios, from simple apps, to more complicated things like, should a Mac see a policy to enable File Vault 2. It would need to be running 10.8.x, have the Recovery HD partition in place and a few other criteria, for example.
