Replication between SQL Server 2005 - 2005
I have found a solution to my problem. Beware though, the steps outlined below broke regular replication (or so it seems). Nevertheless, I was able to get replication running, and now there are no undelivered commands building up in the distribution database:

I Command You To Deliver Those Commands

The solution provided there is to run:

exec sp_changepublication
    @publication = 'xxxxx',
    @property = N'allow_anonymous', 
    @value = 'false'
exec sp_changepublication
    @publication = 'xxxxx',
    @property = N'immediate_sync',
    @value = 'false'