I don't know how the error came to be, but I could fix it by manually deleting every task from the database. Most of my tasks were created automatically anyways, as they are repository health checks. But please note, that may not be the case for everyone, make sure you know what tasks you have so you can recreate them. Also, back up your database before, in case something goes wrong :-)
Here's how I did it, with my Nexus installation being in /opt/nexus and my data directory being in /var/nexus-data:
nexus@my-nexus-server:~$ java -jar /opt/nexus/lib/support/nexus-orient-console.jar
OrientDB console v.2.2.37 (build a7541e7ceeabf592dd9a7b2928b6c023cbc73193, branch 2.2.x)
https://www.orientdb.comType 'help' to display all the supported commands.
orientdb> connect plocal:/var/nexus-data/db/config admin admin
Connecting to database [plocal:/var/nexus-data/db/config] with user 'admin'...OK
orientdb {db=config}> delete from quartz_job_detail
Delete record(s) '38' in 0,047000 sec(s).
orientdb {db=config}> delete from quartz_trigger
Delete record(s) '22' in 0,037000 sec(s).orientdb
orientdb {db=config}> exit
I'd assume that if you had an external database the table names would be the same, I'm just adding the OrientDB commands here because I found using its console confusing, maybe it helps someone else. Unfortunately I could not find out which job was the problem, if someone could find that out we could be more precise in our deletion.
Cheers :-)