Caveat: I'm a photographer, and Pixsy is one of the tools I use to help me find unlicensed uses of my work, but I don't currently use them to recover lost revenues on my behalf, nor have I done so in the past.
As you'll no doubt know, Pixsy's service will first index a photographer's own works either from their hosting service (Flickr, Tumblr, Instagram, Photoshelter etc.) or from a direct upload - that's how it knows what images to search for.
Once it has indexed a photographer's works, it then scans the web for matches and - this is the crucial bit - reports back the information to the photographer, who then decides what action they want taken. If you've received a letter from Pixsy on behalf of the photographer, it's because that's the action they want to take. Pixsy do not send out letters automatically or blindly.
As for your statement that the image file (and your site) have since been deleted on account of you not renewing hosting/domains - well, the way Pixsy indexes sites, it caches evidence of the uses, such as the URL of the page, and the URL of the static image file that would have been on your server. There'll no doubt be legacy WHOIS data that shows you owned the domain name at the time they indexed your use of the photograph referenced in their letter. There may also be a third party record of your website at the proximate date, on a service such as web.archive.org (known as the "WayBack Machine")
In this way, it's a little like having CCTV footage: you might not recall what photographs you used, or when you used them, but if evidence exists to show what was on your site at a specific date and time, that's all that is required to claim an infringement. Should additional third party evidence also exist, that only bolsters the claim further.
You could perhaps search the photographer's name in the US Copyright Office's database to see if they have any registrations on file. If they do, and any of the registrations suggest they are related to the subject matter of the image in question, that would point to the validity of their claim. You also could try to contact the photographer directly if you want to.
Having worked as a photographer for over twelve years, I can tell you that the majority of my peers simply want to be fairly compensated when someone makes use of our work. Before 2011, it was very hard to trace infringements unless you had very deep pockets to pay for means to do so, but as indexing technologies evolved, they became more commonplace and also free to use (TinEye and Google's reverse search being prime examples)
When you work as a photographer, your images are a result of the time, energy, and money that you have poured into your craft. To find your work being used without permission can not only be an indicator of lost revenues, but also quite deflating. Any of my peers will tell you they'd readily engage in pre-use negotiations but care little for the hassles of recovering losses from infringements. That's what attorneys are for - or services such as Pixsy.
What you decide to do is ultimately up to you, but with Pixsy, I'd personally like you to consider that the genesis of the letter/email you have received is from someone who takes their craft seriously - at least seriously enough to expect to be compensated whenever someone uses their work.