There are two different behaviors in the Cade Roux's answer: replacement is successful (when SQL collation is used) and unsuccessful (Windows collation is used). The reason is in type of collation used.
This behaviour was submitted to Microsoft nearly 4 years ago:
Q: When trying a replace a NUL character
with replace(), this works is the
value has an SQL collation, but not a
Windows collation.
A: This is due to the fact that 0x0000
is an undefined character in Windows
collations. All undefined characters
are ignored during comparison, sort,
and pattern matching. So searing for
'a' + char(0) is really searching for
‘a’, and searching for char(0) is
equivalent to empty string.
The way to handle undefined character
is a bit confusing, but this is the
way that Windows defined to sort them,
and SQL Server conforms with the
general Windows API.
In SQL collation, there is no notion
of undefined character. Each code
point is assigned a weight, that's why
we don't see a problem there.
but unfortunately, it is still undocumented.
So, it seems the only one solution is to change collation to SQL collation (e.g. SQL_Latin1_General_CP1_CI_AS
may be used as well).
* I removed my previous answer as unnecessary