This is a known issue that indeed has been fixed in CMS 6 R2.
I forgot to mention that I'm using CMS 6 R2, and the database is an upgrade from CMS 6 R1 to R2.
I would setup logging for the scheduled job and look for clues, see http://world.episerver.com/Documentation/Items/Tech-Notes/EPiServer-CMS-6/EPiServer-CMS-60/Logging/ and http://world.episerver.com/FAQ/Items/Debugging-the-scheduler/ Maybe the IIS is configured to go idle after x minutes so the job is stuck in running mode.
'Published Delayed Page Versions' job gets stuck in 'running state' (The status is: 'The job is running.')
It prevents other jobs to be executed, so I have to start it manually. But it gets stuck again and again and again... :)
Any help would be greatly appreciated!