OK, I am passing some convoluted urls back to apache and evidently
apache does not like by backspace. Is there anything that I can do to
have apache accept them?

The following works just fine:
http://mydomain.org/DE/d^|[^;:]{7}(;|:|$)/o:-DE;US;-US

but the following fails (the only difference is [^;:] goes to \w):
http://mydomain.org/DE/d^|\w{7}(;|:|$)/o:-DE;US;-US

In this case I get:
Not Found
The requested URL /DE/d^|\w{7}(;|:$)/o:-DE;US;-US was not found on
this server.

To me, the fact that it shows me the request as I gave it implies that
apache has some issue with that backspace character.

my rewrite log does not show the request being processed, error log
shows nothing. The access log shows:

127.0.0.1 127.0.0.1 - - [18/May/2007:11:16:45 +0200] - "GET /DE/d:
(%5E|%5Cw%7B7%7D(;|:$)/o:-DE;US;-US HTTP/1.1" /DE/d^|\\w{7}(;|:
$)/o:-DE;US;-US MyDomain.org mydomain.org 404 232 "-" "Mozilla/5.0
(Windows; U; Windows NT 5.1; en-US; rv:1.8.0.11) Gecko/20070312
Firefox/1.5.0.11" - "-"

Thanks,
Csaba Gabor from Vienna