Gravatar have added an option to the 'd' parameter, meaning that if you pass in d=404, you get a 404 page (instead of some 302 redirect to a default picture) if there's no picture, rather than having to use heuristics.
Though you said you know about the d parameter, do you know it actually returns a redirect header when applicable? So, the following yields 302 Found because the avatar does not exist:
HTTP/1.1 302 Found
...
Last-Modified: Wed, 11 Jan 1984 08:00:00 GMT
Location: http://www.google.com/images/logo.gif
Content-Length: 0
...
Expires: Sun, 26 Jul 2009 23:18:33 GMT
Cache-Control: max-age=300
Seems to me that all you need to do is add that d parameter and check the HTTP result code then.