Unfortunately I cannot re-create the issue on my test servers, it's working for me, but I might have an idea. Maybe because of the permalink structure the page number variable is reset or removed for some reason and the search displays always the same first results – because it thinks it's on the first page always.
I've quickly worked out a minor modification that might work for you. Open up the wp-content/plugins/ajax-search-pro/includes/hooks.php file on your server and replace it's content with the contents on this link: http://pastebin.com/raw.php?i=H6Gpffj4
Don't forget to make a back-up copy just in case! Hopefully that will help.Best,
If you like my products, don't forget to rate them on codecanyon :)