I fast traveled to Solitude from out in the wilds and my Thrall didn't come with. No biggie, I expected him to show up once I entered Proudspire -- but he didn't show. I checked the stables outside the city and he's not there, either. Any idea what happened?

Hes likely idling somewhere, dead thrall ai is pretty bad.

if you really want to find him you can work some magic in console but i realize some players are adversed to this route.

Did you fast travel to Blue Palace?
The thralls don't travel there with you and you have to wait a bit for them to catch up.

edit: They also get stuck in Broken Oar Grotto for me. They enter fine, but refuse to ever leave.

I have found that sometimes when whatever cell you got your thrall from resets, it will teleport your thrall there.

Actually, we had just been in Broken Oar Grotto. I assumed my Thrall (http://elderscrolls.wikia.com/wiki/Benor) exited the cave with me; perhaps not. I'll pull up an old save and check. Thanks!

Oh trust me, he didn't leave the cave. I'm willing to bet one shiny quarter he's still standing at the entrance/exit slope.

Maybe I shouldn't be so confident, but after it happened to me I looked it up on the internet and saw other people needing help with the same situation (across multiple platforms too). It's my best guess your dead thrall is still standing in that cave.

One cool thing I noticed is that if your thrall decided not to enter the zone with you, like stays outside when you enter a dungeon, you can go back to casting other pets like normal, like two dremora lords.

Then after you leave and fast travel somewhere, you'll hear that ever familiar groan from behind you. (as long as you ditched the dremora lords before leaving the dungeon)