>> We run maintenance plan created SSIS packages to backup our databases.
>> The final step is the cleanup of the jobhistory. We see the occasional
>> deadlock coming from sp_maintplan_delete_log.

Is it possible that two maintenance plans are calling this procedure
at/around the same time? If so, my suggestion would be to create your own
job that deletes ALL maintenance plan logs, say once a day, by passing in
only the @oldest_time parameter. And then set each maintenance plan to not
delete its own logs.