Complaining about overuse of "very" seems to be a very common peeve: Merriam-Webster, Columbia Journalism Review, Grammarcheck, Daily Beast. Criticisms generally boil down to it being overused and that overuse is repetitious (and repetition in writing is usually considered bad). "Very" has a tendency to be vague or imprecise, or at least to give an impression of imprecision. There are often better ways to increase the force of writing than just sticking "very" in all over the place: rather than say "this is very very bad", either factually explain why it is bad, or use more sophisticated rhetorical devices (e.g. litotes, hyperbole, irony).
So while your examples are perfectly grammatical and not hideous, and would be fine especially in speech or informal writing, you could rephrase them to be more specific. Say "I find search engines invaluable/essential", and explain why or for what purpose. Most people would be very sad if their dog died, so "He's very sad because the dog died" isn't really news - "he has been crying all night because his dog died" or "the dog he grew up with and played with every day has died" would convey more information.
There are certain circumstances where "very" is ungrammatical or very awkward, but they don't apply here.