Yes, Clean URLs should work for both the free and the paid licenses.
I'm not sure what else you should check. Usually, enabling mod_rewrite is all you are to do to enable Clean URLs on an Apache server.
Did you check this section too?
http://kb.x-cart.com/en/general_setup/setting_up_seo-friendly_urls.html#troubleshooting
It may be that your server settings prevent X-Cart from using its own .htaccess file (thus disabling mod_rewrite rules defined in it).