Dear gav,
Having been out to both Latvia and more regularly Estonia, I can confirm that both these countries have filler stations like here with 95 and 98 octane fuel. I have never ridden there yet, but I doubt you'll have a problem.. My advise would be to fill-up in the larger towns, just to be sure. You could cross Estonia on a tank full anyway.
eitherway, based on the fact the you often see Mercs Beemer and Porsche in the cities, I'm sure they would come off worse than a bike if running on crap fuel...
Hope that helps.