"...So, is it illegal for me to download MP3s of the LPs I already own?" - Yes it is illegal.
"What if some of those LPs aren't in my possession, but they are in storage with a third party?" - Don't know about what you mean by that.
"How about downloading MP3s to replace CDs/LPs that have been purchased and subsequently lost?" - Thats also illegal.