Deleted backlinks

Recently I found that links that i've paid for were deleted and emailed the sites. One of them told me they've sold the site and can't do anything. The other told me that was penalized by G and because my link was live for almost 2 years he thinks that the service is fulfilled. I've paid not so small amount of money for those links and now I feel like I can't do anything. I have an invoice but opening a dispute in PP is until 180 days. What would you recommend me?
Thanks

It's a tough one, I don't want to sound like a fatalist, but there's probably not much you can do at this stage unless you had some kind of a formal agreement, which is not the case usually.