Have you checked
atomhost ? they are really cheap and will be offering in a week or so Individual database (actual is shared) and they also offer free e-commerce.
Check them, they are really worth it ! I signed up with them and they are perfect ! Every time we need a module they add it to the server (we wanted streaming media, they added it, we wanted individual database, they are adding them, I wanted mod_perl, They are adding it etc ...)
they also have a very good support via their forum, check them they are really worth it !