that's true. every hosting provider should provide you with mod_rewrite. i had about 10 providers and everyone accepted this mode. so far i did not heard anything like this. very strage for me. and be sure if you will get a shared hosting i can garantee you that this the cheapest way to start your website.