Late answer, I realise, sorry. I hope this is still relevant for you:
First, I'm echoing the comments your got in response to your post. PHP5 is the way to go.
However:
I'm in the middle of a callback during
an xmlrpc request and it's required to
return a specifically structured array
no matter what.
If you can vouch for that the program cannot possibly continue without getting a structured array back, and you absolutely have to work with PHP4, then an exit() or die() with detailed error information will get you much the same effect as a fatal exception would.
That's far removed from being graceful, of course. If you want something catchable, then return values and if-checking the result are your best bet, unfortunately. There are some standard ways of passing back specific error objects, but it's still the same thing - return the error object, if-check whether the result was an error object, react.
Still, take a look at PEAR's error object.