An object should never be in an invalid state. The object should throw an exception as soon as the consumer tries to set an invalid state on it.
Your object could be in an unusable state (say it's a database connection object, and it hasn't connected yet), in which case it should have an IsConnected flag, or it should follow the state machine pattern so that the object's state is still valid in its own right.
And since your ToString() overload presumably doesn't take any arguments, it should never be the caller's fault that it would throw an exception.
Therefore, no, I can't think of any exceptions that ToString() would throw.
Edit: In the case of the pastebin code, the best way to go about doing this would be to consolidate the query parameters in a separate class -- call it SearchParameters or something.
Populate that first, and then pass that into a class that'll generate the SQL code. If when you pass the SearchParameters object into SearchQuery (probably through the constructor so that you can make it immutable) the parameters are invalid, you can throw an exception there.
That way if your SearchQuery object ever has more methods that rely on there being a valid search query, you won't need to repeat the validation code, and of course, ToString() will never throw an exception.