Aqua will use something called "ESEARCH" (enhanced search) if the server says it supports it, to speed things up and save traffic.
Can't speak for all apps, but K9 or stock Android Email don't... and then if you're comparing to Cloud Magic or Accompli or MyMail, that's completely different, but I'll spare the details.
I've seen servers that advertise ESEARCH as supported, and yet can't deal with it.
Please try this:
1 - Update to the latest -dev9 version of Aqua
2 - Long press the account -> options and folders -> IMAP options -> turn off "IMAP optimizations". This will disable the use of ESEARCH command.
Or could be something else, of course...