I too have problems with the pagination.
It is stuck on 10, like yours Milbo, even though I have set "Frontend default items per list view" to 20.
I have tried changing to a standard joomla template and default category template, but then I get no other choice than 10 from the droplist.
If I use my own template, it shows the values I have chosen in virtuemart configuration, but choosing any of them still makes it only show 10.
Joomla 2.5.14
Virtuemart 2.0.24
All Sef is off and cache is turned off
The frontside language is not English
I got this problem when I updated to 2.0.24
I usually always get problems with pagination in virtuemart each time I upgrade virtuemart in some way or the other

I do consider this a bug also, that using catalogue mode, and using "Do not display product" in "Action when a Product is Out of Stock" makes the pagination totally wack. If pagination is set to 10 for example, it can show 2 products on one page, 5 on the next one then perhaps 10. So if only 2 products are showing on one page, it means 8 products are out of stock but it doesn't replace them with products that are. I also think the counter it generates for products in a category also includes items that are out of stock.