Using backtracking. I do not intend to post new riddle.
! The Lusitano belongs to Majestix if and only if the Frisian belongs to a mage.
! The Mongolian belongs to Fred if and only if the Lusitano belongs to a mage.
! Majestix is a lord if and only if the Lusitano belongs to a footpad.
! Limerick is a footpad if and only if the Lusitano belongs to Majestix.
! The Frisian belongs to a mage if and only if Fred is a lord.
! Majestix is a lord if and only if the Mongolian belongs to Fred.
a footpad, a mage and a lord
a Frisian, a Lusitano and a Mongolian horse
Fred, Limerick and Majestix
Known that first is invalid
Known that second is invalid
Known that third is invalid
Lusitano !-> Majestix
Frisian !-> mage
Limerick != footpad
Mongolian !-> Fred
Lusitano !-> mage
Majestix != lord
Lusitano !-> footpad
Fred != lord
Lusitano -> Limerick lord
Frisian -> Fred footpad
Mongolian -> Majestix mage