The WordPress Memory is something not easy to deal with. If the standard way is not helping (don’t rely on the WP_MEMORY_LIMIT constant, it’s conceptually broken, use ini_set in wp-config.php instead), then you can only throw hardware on it or hack the core.
Please check if you’re using a recent PHP version on your system. If that’s something with PHP 4 upgrade to PHP 5.
If you’re running on PHP 5 downgrade to PHP 4 (<- that is for a test and only if any other resort is available. You should consider that bad practice because it will bring you no-where in the near future)
These two advices might sound funny, but I know of both: WP PHP 5 sites that ran out of memory but then worked on PHP 4 and the other way round. Just give it a try.
These are best general tips I can give. The topic is broad, we normally handle that individually.