we learned a while back that deviled eggs are called that because they were, at the time, considered to be "devilishly" spicy (similar to Mexican/Southwestern foods being called something like "Diablo tacos" or whatever) and
either the recipe for deviled eggs has changed a lot over the centuries, or medieval people had no tolerance for spicy food