I agree that these words are incredibly overused. (uh oh) But "impossible to believe" is not the only valid definition. Robert pointed out the definition, "astonishing." Also, "difficult to believe" is a good definition. So I don't think most people incorrectly use these words, they just overuse them. I was just wondering if everybody only said "very" and "very good" how soon we would get tired of hearing that. Variation is a key to interesting conversation.
What other words or phrases could be used?
Incredible stopped meaning "unbelievable" quite some time ago. Similarly, advertisers who claim fantastic savings or fabulous performance don't expect anyone to think they mean the savings or performance are nonexistent and imaginary.
We can probably thank Neil Patrick Harris for having a similar effect on the word legen (wait for it!) dary.