Update and workaround for this issue:
Our IMAP settings in our hosted Gmail were set to scan "All Messages" and "Sent Messages" Unchecking these settings in Settings->Labels resolved the issue of jobs not getting processed, and provided us with better processing time (under 1 minute for most jobs).
We still have IMAP Timeout Exceeded errors, but before the fix, they were exacerbated by the IMAP session scanning all the messages. Google recommended setting a longer timeout, but the IMAP timeout for Mobileprint is not configurable.
Thanks to Pharos Support (Greg) for working the problem and finding this solution!