So the short version of the story is I was deciding what game to buy this month. Burnout Paradise Remastered or Surviving Mars. I have EA Access on Xbox One so I have the 10 hour demo, and playing it made me remember how much I liked the game. So I was thinking "well I already own it on PS3, so why not download it and see if I need a better looking version".

Well, I went into the PS3 store and Burnout Paradise is no longer listed. I did a word search, I even went through all the games listed alphabetically and it's not there. I had to go into my transaction list and scroll all the way to 2008 to find it (and as someone who has had PS+ since before it was cool, I had a lot of stuff to scroll past).

I could redownload, and it's patching right now, but when did the game get removed from the store?

Servers for the original version of Burnout Paradise were shut down a while ago. More than likely the reason it's been delisted from PSN on PS3.