Hi,
To fix the pagination problem eventhough the SEF is enabled.
Try this:
Open this PHP file:
ROOT/templates/<yourjoomlatemplate>/html/category/default.php
(default.php, defaultlist.php, flexv2.php or whatever you have chose from the VM Configuration. There are 6 different layout, and you are using only one of them. Open the PHP file that you are using in your webstore)
And find this HTML line:
<div id="bottom-pagination">
And change it with this:
<div id="bottom-pagination" class="vm-pagination">
(be aware, you will need to do it in 2 different place in the same PHP file, since there are 2 sections where the pagelinks show off. One at the top of the category page, and one at the bottom)
This should solve the problem even though the SEF is enabled.
Please let me know the result.