You're saying this is happening only when displaying your payment modules in the admin.
Since the admin isn't doing anything intensely complicated with actually processing any transactions when showing that list, I suppose one way to get around your server's memory problem could be to deactivate other payment modules which you're not using, thus leaving some memory available for other modules which you *are* using.
So, based on the list you gave near the beginning of this discussion, I'd suggest you go into the settings (click "edit") for the "Credit Card - Offline Processing" module, and click the "Remove" button. Same with the Check/MoneyOrder module.
That might give you a tad more room until your hosting company can make its custom memory configuration actually work for you.