Building on the 'cure the plague spirit' idea of Empirate, you could send them to China to get rare, magical[?] herbs for plague medicine. Throwing in a few Mongol warrior archers would be a fun twist, but I'm truly not sure whether this would fit in with your proposed 'timeline' if you're going for any historical verisimilitude.
China would be a stretch, but Persia or Arabia might be within reason. Maybe a sha'ir knows how to retrieve a necessary component for the cure from the realm of the Efreet...
