If you are hosting your WCF Data Service on top of IIS+ASP.Net/WCF, then you may discover that there are certain characters that will cause the server to throw when they are contained in entity keys. The result is either a 400 Bad Request or 404 Not Found...