After some investigation, we found that: Windows Firewall is disabled on both server and client machine. Running Portqry from a command window also show that correct information was returned by SQL Browser and the UDP packet is received by the client machine. However, the application (specifically, SQL data access driver layer, e.g. SqlClient, SNAC) still could not finish the SQL Server configuration discovery process. The strange part is that everything is fine if the app runs as a standalone app. If it runs as a service, we see the error 26.
Netmon trace shows that no request UDP packet was sent out of the box. The packet must be lost somewhere. Meanwhile, we found Windows Firewall Service (MpsSvc) is still running although we have disabled Firewall in "Windows Firewall with Advanced Security" configuration tool (run wf.msc from command window). We tried to disable the Firewall service and the issue disappeared. So, obviously, the outgoing UDP packet is blocked by firewall. We engaged with Windows firewall team and found the root cause.
What happened is that since Windows Vista, Windows enhanced security practice for service, which is called Windows Service Hardening (WSH). A service developer can install WSH firewall rule for a specific service. WSH firewall rule has higher priority than regular firewall rules and it would take effect even if firewall has been disabled through wf.msc. In addition, you cannot turn on/off WSH firewall through wf.msc. You can only configure it through programming as of now (or manually edit some registry).
For the customer's case, he has a WSH firewall rule which block all outgoing UDP packets. So the solution is to put exception so that outgoing UDP packet targeting remote UDP port 1434 won't be dropped. Another thing worth mentioning is that WSH firewall will block packet even if the target is local machine. (Usually, Windows firewall never blocks local traffic.)