To follow up on my own message, it appears that the pageSize header is not being sent as part of the message from Flex to the JavaAdapter, but I have no idea on why. I even added a 'myDataService.pageSize=100;' in the flex client. :(
To follow up once again (for the sake of future developers :), I found the answer. Our project consists of multiple sub-projects. While I had set the -service flag for the main project, the sub-project that contains the code did not have the flag. Adding that compile flag fixed the problem.