Just to confirm, you are using mod_pagespeed with nginx proxy_cache - correct?
If yes, you can check the proxy_cache access_log to see what kind of PURGE URLs are returning 404s. You should be able to grep for whatever ModPagespeedDownstreamCachePurgeLocationPrefix you have used in your config.
If the access log does not help, you can still use the instructions I gave for checking the apache mod_pagespeed logs to understand what is happening to the PURGEs. Re-pasting:
'Also, if you could enable info logs in apache for a short duration and check the apache error log, you should find lines starting with "Purge url is" for every attempted PURGE. You could grep out these lines and check if these seem to be pointing to your Varnish server (host:port) correctly. If any of the PURGE requests are failing, the 3 or 4 lines following the "Purge url is" line should indicate if the purge failed due to the connection being refused etc. Could you check and let us know what you find?'
As long as you are using the same cache key ($ps_capability_list$1$is_args$args) in both the proxy_cache_key and the proxy_cache_purge lines, the User-Agents will get accounted for in the same way. This is because we store and pass along the incoming request headers (with UA) to subsequent PURGE requests for the page (if any).
Thanks,
Anupama.