Error 'You have sent us an Illegal URL or an improperly formatted request'

Scenarios That Trigger This Error:

As documented in the SOAP API developer guide's Implementation Considerations section - 

"The character set for your organization depends on the Salesforce instance your organization uses. If your organization logs into ssl.salesforce.com, then your encoding is ISO-8859-1. All other instances use UTF-8."

As a result the following requests may receive the mentioned response:

• Request containing non UTF-8 characters in the URL (including the query string) or in cookies.
• POST requests containing non UTF-8 characters in the body when Content-Type: application/x-www-form-urlencoded is used. 

Encoding Notes:

• URLs using %u<xxxx> encoding will fail. These must be properly URL encoded instead.
• When Content-Type: application/x-www-form-urlencoded is used, the request payload must not include non UTF-8 characters. Compressing text using gzip, deflate or similar methods may produce non UTF-8 characters.
• When Content-Type: application/x-www-form-urlencoded is not used, the payload may contain compressed content and the Content-Encoding request header is used to decode the payload.
• For cookie values, use encodeURIComponent() or encodeURI(). Do not use the deprecated escape() or unescape() functions as these are obsolete in ECMAScript and likely to stop working any time in browsers. 
• Due to XML compliance requirements, SOAP API requests have an additional restriction: Salesforce supports only the basic UCS-2 encoding (two-byte, Basic Multilingual Plane) and does not support extended UCS-4 characters.

Recommended Request Body Formats:
There are two common formats for request body content:

• multipart/form-data encoding (RFC7578): This is the recommended format when sending international characters to Salesforce.
• application/x-www-form-urlencoded: Unicode characters are supported, but only when encoded using UTF-8 percent encoding. Because the charset for this format is not communicated in the HTTP protocol, and as such there is no way to determine how content is being encoded, whether it is/was SJIS, Russian, Korean etc. Salesforce always assumes UTF-8 when decoding.