Web service response encoding issue

The first thing to do is to sniff what's actually being sent, in terms of the headers, the XML declaration and the bytes forming the text itself.

Fiddler is good as an HTTP proxy, or you could use WireShark to sniff at the network level.

Once you've got those three bits of information (the Content-Type header, the XML declaration and the bytes making up the pound sign) if you update your answer we'll see what we can do. It does sound odd, as usually ASP.NET just gets all of this right.

What does your client side code look like? Is that just the normal .NET web service client code as well?

EDIT: Try to find a binary (hex dump) display in Fiddler so you can find the bytes.

However, I strongly suspect that the problem is merely with dumping the result to the console. Here's a bit of code to use to dump the unicode code points:

static void DumpString (string value)
{
    foreach (char c in value)
    {
        Console.Write ("{0:x4} ", (int)c);
    }
    Console.WriteLine();
}

I suspect you'll see an 00A3 in the output, which is the Unicode for the pound sign. That means the string has actually reached your client fine - but writing it out to the console is failing.