After reading a little in this thread, I've come to the conclusion that relying on exit() to clean up after you is generally not a good idea.

What would you consider to be the best way to handle critical errors without some crazy C++ like exception handling system?

I guess you could add atexit() after every memory allocation that you know is going to remain in memory during the program's entire lifespan, but how should you deal with objects with an unknown lifespan?

This is just a very crude example, but assume that you want to terminate the program if the foo() call fails. How should you deal with freeing the previously allocated memory in a situation like this one? Using atexit here could get a little tricky since you could end up in a situation where you might've already freed some of the dynamically allocated memory. I guess one way to deal with this could be to set the memory pointer to NULL after you free it, and then check for NULL in your atexit handling.
Code:
memory = malloc(something);
if (!memory)
// Error handling

.
.
.

if (foo() == ERROR)
// Something went wrong here, terminate program