Maybe the DM could pinch ideas from Heralds of Valdemar- you don't find the mount, the mount finds you.

But then, in those books, the mount was more friend and partner, than minion.