Three of my grandparents were Eastern European, back at least several generations. I recently discovered that I am less than 25% Eastern European, the rest being Western European and other. How likely is this?
On average, 25%, because you have 4 grandparents, and all of your genetic material came from them as a collective. Of course it's possible to be more genetically similar to a particular grandparent by random assortment of chromosomes, but the average will be 25%.
Genetic tests can't tell you what your ancestry is (companies implying this are probably misleading you on purpose). At best, they can tell you how correlated certain features of your genome are with people from a certain geography. Even people who are currently live in Eastern Europe will not test as "100% Eastern European." There is far too much mobility and breeding of populations across geography and far too much variation within populations.
[English is not my native language]
I know a girl (say, Natalia) who took a DNA-test at National Geographic, while her half-brother (say, Sam) took one at 23andMe. They were both told that they had one-eighth of Ashkenazi origins. And in fact, they share an Ashkenazi great-grandparent. So, I conclude that they have one-eighth of this great-grandparent, and the precision was so great that I am inclined to believe that there is a high probability that it is the same for everyone : one-half of each parent, and one-fourth of each grandparent.