Could this be just a case of Google screwing me up for no reason at all?
No, you answered to yourself already.
Aside from the above, I see absolutely no reason for this penalty and honestly I really doubt the above points warrant any kind of penalty. I run a clean website, which focuses on quality and I never overdid SEO or did any kind of spam.
This is SEO spam:
- I sold about 6-7 links since the website was born 3 years ago. Just 2 in the last 2 years and I think only 4 of those links are still in place
- I have about 15 link exchanges, all off them created 2-3 years ago
You do not care where you link to via useless exchange or where you sold links to. Some footers of those sites look even more awful than yours (xxxp://tennis-predictions.com/).
If you talk to God, you are praying; If God talks to you, you have schizophrenia.