I also tested sed to see if it's the system supplied regex library, but that's all ok:
$ echo "abc123" | sed -e "s|123|def\0ghi|g"
abcdef123ghi

$ echo "abc123" | sed -e "s|123|def\\0ghi|g"
abcdef123ghi

$ echo "abc123" | sed -e "s|123|def\\\0ghi|g"
abcdef\0ghi

$ echo "abc123" | sed -e "s|123|def\\\\0ghi|g"
abcdef\0ghi

Thank you for this bug report. To properly diagnose the problem, we
need a backtrace to see what is happening behind the scenes. To
find out how to generate a backtrace, please read
http://bugs.php.net/bugs-generating-backtrace.php

Once you have generated a backtrace, please submit it to this bug
report and change the status back to "Open". Thank you for helping
us make PHP better.

Markus,

Unless you have some tips, not covered in the generate backtrace links, the problem only occurs with the CLI - I cannot reproduce it in apache.

As said:
I've compiled php with --enable-debug, used:
gdb -exec sapi/cli/php -core ./php.core

And:
gdb sapi/cli/php
Copyright 1998 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i386-unknown-bsdi4.2"...
(gdb) set args -e -c /chroot/home/mdev/php4-200206160300/php.ini-dist -f /chroot/home/mdev/php4-200206160300/run-tests.php
(gdb) set environment TEST_PHP_EXECUTABLE=/chroot/home/mdev/php4-200206160300/sapi/cli/php
(gdb) run
Starting program: /chroot/home/mdev/php4-200206160300/sapi/cli/php -e -c /chroot/home/mdev/php4-200206160300/php.ini-dist -f /chroot/home/mdev/php4-200206160300/run-tests.php

CLI ist just fine, it's even easier to debug. But I think your last submit missed the output of BT unless I'm missing something?

Heck - this is even more complicated.
If I take the 'FILE' section in 011.phpt and put it in 011.php, then use:
$ /chroot/home/mdev/php4-200206160300/sapi/cli/php -e -f ./011.php
abcdef123ghi

all is fine. With make test it failes.
The output of gdb is complete, just in case, here it is again:
---Type <return> to continue, or q <return> to quit---
#0  0x486b660f in memcpy () from /shlib/libc.so.2
(gdb) bt
#0  0x486b660f in memcpy () from /shlib/libc.so.2
#1  0x814ed64 in ?? ()
#2  0x814f375 in ?? ()
#3  0x814f4c0 in ?? ()
#4  0x81c473a in ?? ()
#5  0x81b3d1b in ?? ()
#6  0x81851f1 in ?? ()
#7  0x81c9fdb in ?? ()
#8  0x806d8ce in ?? ()
(gdb)

I've also topped make test while running, to see if I go through any shell limits, but php doesn't even go above 5 Megs and I can take 384 Meg in this shell.

Did you compile using --with-regex=system?  That is known to be broken on some platforms.

Nope, no regex config flag at all. So the php default is used.

Oh - and since it forks off another CLI executable, I can't get to that one in gdb - tried 'set follow-fork-mode ask', but doesn't help a bit.

Dupe of #15829.
Please compile PHP with --enable-debug and provide a backtrace and post it on #15829.

Ok:
1) How did you find it - oh you posted it. I tried \0 in ALL categories and it didn't yield any results. Searching the database needs improvement.

2) I did compile with --enable-debug and I gave a backtrace.

This bug has been fixed in CVS. You can grab a snapshot of the
CVS version at http://snaps.php.net/. In case this was a documentation 
problem, the fix will show up soon at http://www.php.net/manual/.
In case this was a PHP.net website problem, the change will show
up on the PHP.net site and on the mirror sites.
Thank you for the report, and for helping us make PHP better.