I don't know if this will help or not, but I've noticed that in some segments of some executable binaries, strings are stored in arrays of integers, so that in a hex browser, the string IBM PC-DOS would look like:

I.B.M.P.C.-.D.O.  49 00 42 00 4d 00 20 00 50 00 43 00 2d 00 44 00 4f 0
+0
S.                53 00
[download]

Your best bet, when you're after replacing text in a file with 8-bit characters, is to use a hex browser to look at the text you want to replace and find out how it's actually stored, not how it's displayed when printed by the program.

In the above example, you could match "IBM" with:

/I\x00B\x00M\x00/
[download]

Or match and replace with "BAR" using:

s[I\x00B\x00M\x00]{B\x00A\x00R\x00};
[download]

P.S. I could have the byte order wrong in the example above, but if your text is stored this way, you'll understand what I'm referring to.