I tried different versions of virtuemart and did search in them and found that there is a fundamental error in virtuemart component search core which result in pagination problem. Also I have tried some ajax search modules but all of them use built-in search functionality of virtuemart which will result in same problem. I want to know if your module has same behavior or not. I mean if your module has its own functionality for search or it uses the virtuemart built-in search?