There are times when you can't do anything with exceptions. Running out of memory is one example.
In the programming languages I've used, for private non-exposed methods/functions I don't put any, unless there is a good reason (like its critical I track this problem, or provide a more helpful error to improve the existing error message). In these cases, I blindly assume that the cleansing has already been applied to any data passed in to it.
Public methods/functions usually have some form of checking for invalid inputs, as they are the public API into your system. This would be the place to have them, as all input is evil.
Also exception handling is more to do with dealing with the system in an inconsistent state. Is it recoverable? This is where I personally draw the line. If there is a threat of internal state being corrupted, throw it.