Even in 2.5, __str__ is allowed to return a Unicode object;
we could change BaseException_str this way:

Index: exceptions.c
===================================================================
--- exceptions.c	(revision 61957)
+++ exceptions.c	(working copy)
@@ -108,6 +104,11 @@
         break;
     case 1:
         out = PyObject_Str(PyTuple_GET_ITEM(self->args, 0));
+        if (out == NULL &&
PyErr_ExceptionMatches(PyExc_UnicodeEncodeError))
+        {
+            PyErr_Clear();
+            out = PyObject_Unicode(PyTuple_GET_ITEM(self->args, 0));
+        }
         break;
     default:
         out = PyObject_Str(self->args);

Then str(e) still raises UnicodeEncodeError,
but unicode(e) returns the original message.

But I would like the opinion of an experimented core developer...