Regarding stores that sell small shoe sizes, what city / country do you live in?
Perhaps someone near you can suggest stores that are local to you?
In my travels, I have noticed that children's shoes generally sell for less then adult shoes, so perhaps you can even look at the youth section of a shoe store and see if they have something that suits your tastes?
Happy hunting!