Examples? Shall we take turns guessing the names of these elusive spam-free providers? Your non-answer reads to me as, "Just don't use any providers that you can actually afford, and you'll be fine!"
(Sorry if this comes across as grouchy--I can't sleep, and I have to get up early tomorrow.)
I use one in my country (Poland), and I use it since a little longer than
Amazon entered our market. I don't think such a regional provider would be of
much use to you, unless it operates in your region, of course.
What my comment boils down to is to avoid big hosting places.