A few days ago one of my cats followed me into the Nether. I'm guessing it met an untimely demise because I haven't seen it since. I don't know if cats can teleport from the nether to the overworld. I've returned to the Nether a few times since then and there's been no trace of cat. I read that Ghast sounds are actually recordings of C418's cat. I like to think that my cat is searching the Nether for that "other cat" but it's more likely that he plunged into a sea of magma.
Today, I rode my horse to my friends house (on my server), then, I forgot my horse there, and when I went back for it, it was gone. I spent half an hour search for it. I didn't find it. It was my best horse, too. =/
Once, I was on a plots server. I had a pet horse named Franco. He had white fur, and diamond armor. I usually just let him roam around my plot, and I he usually didn't go too far(my plot didn't have any fences). But one day, when I came down from building my giant roller coaster, he was gone. I didn't know where he went. And I couldn't get another one, since spawn eggs were recently disabled on the server. I assume he ran away to Mexico....
I lost my horse in a nether fortress. It was my favorite one, and yet I lost him in a castle in hell :(. I shouldn't take horses to hell.
I also lost a pack of 16 wolves, because I hit a villager and they came at him. My pet iron golem protects the village, so he got angry and the results weren't happy.
I lost my pet cat once. I had tamed the cat in a jungle on the third day of me playing on this world. I called it Holly, after my real life cat, and we had many adventures together. She was my first minecraft cat as I was never good at fishing. Sadly, a year later of still playing my world, I was mining and had previously forgot to sit my cat down. She followed me into the mine and I did not intervene. Sadly, when I found diamond I got my Fortune I pickaxe and mined it, only to find lava below. I held crouch and Holly plunged into the fiery flames.
I lost my wolf Billy. He followed me into my mine because I never sit him down in his pen, and he glitched through the fence (in 1.2.5, fences were really bad). I accidentally hit him with my pickaxe and he attacked me. Instead of killing him, I buried him in a hole, then put up a sign. It's like a grave but I think he is alive, because my mine is right under my house, so he won't have despawned.