Fatal Error memory limit exhausted showing when it shouldn't be

I’ve been getting the “Fatal Error – Memory Exhausted….” notification with a particular plugin, which is critical for my site. When I deactivate the plugin it goes away, and comes back when activate it again. I called my hosting company to get my memory increased, but they said it is still low, so they didn’t know why I would be getting the error.

Any idea what could be causing this or how I can fix it?

Thank you.