It is a simple SEF URL issue, and it happens sometimes. (when your friendly-URLs are already generated with IDs in it, but somehow your Virtuemart doesn't want to use them).
Anyway, the solution is quite easy.
Open your VM Backend, and look at the screenshot:
Flexible Support Team
The administrator has disabled public write access.
That solution normally fix the problem. I don't know why it didn't work out in your case.
Can you please make sure; you don't set manual pagination rule differently?
Look at screenshot:
Please email me your joomla admin account to This email address is being protected from spambots. You need JavaScript enabled to view it. and let me check it out for you.
Cheers.
The administrator has disabled public write access.