Proper urlencoding of spaces in formulas syntax

The behavior for #2 is actually documented, because Salesforce URLENCODES the final output from the custom link, regardless of your specific URLENCODE-ing:

Custom buttons and links with URL content sources have separate encoding settings. If you use the URLENCODE function to encode a custom button or link that has an encoding setting specified, Salesforce first encodes the URL according to the custom button or link setting, then encodes the result. For example, if the URL in a custom link contains a space and its encoding setting is UTF8, Salesforce first encodes the space to a plus sign (+), then the URLENCODE function converts the plus sign to its character code, %2B. -- Operators & Functions Documentation

The same logic explains #3: You replace "" with %25, and then the final encoding replaces the % with %25.

Work-Around

Use a Custom Field instead of a Custom Link. Field Type: Formula (Text):

HYPERLINK("http://example.com/path?customer="&SUBSTITUTE(Name, " ", "%20"), "Link to Customer in Other System")