I'll admit I've only been reading bits and pieces of the timeline (though I love the premise), but there would have been tigers as far west as the Caspian at this time in history.
Still a bit of a trip for the delivery man. I suspect he meant lions, but perhaps there was an exotic animal trade for royalty I don't know about. I know back in Charlemagne's day the Caliph sent him an elephant as a gift, but I assumed that was fairly exceptional.