I think this might be an issue with Gravatar and not Stack Exchange. I'll explain my reason for thinking this later in this answer.
First off, there is possibly a way to get your old gravatar back, adapted from Caleb's answer on Meta Stack Exchange:
Go to the Wayback Machine.
Enter the URL for your profile page. If you're lucky, it's been archived there. ...
A fairly recent article on ArsTachnica, regarding how using Gravatars can leak an email address has prompted us to make some changes to how we produce the gravatar hash (under certain circumstances).
Looks like this happened here.
This will be fixed in the next builds.
You were experiencing a bug that affects Gravatar/Identicon users who have capital letters in their email address. Because we request icons of various sizes, we build Gravatar requests on demand using various data including email addresses. The algorithm we're supposed to use is MD5(ToLower(email) + salt) but our ...
When you upload a picture to use as a (Gra)vatar, it gets uploaded to SE's Imgur account. In that sense, it cannot be deleted.
As an approximation, if you upload a different image (even if you do not use it), then that image will become your option for an "uploaded picture" (pushing your previous uploaded picture into the æther).