SQL Server – Causes of ‘Recovery Completed for Database’ Log Messages

_{Community wiki answer originally left as an edit to the question by its author:}

The problem was that the database property AutoClose was set on.

The solution was to set AutoClose to false.

If you are saying that some databases are being skipped, then I would bet money that you are using sp_MSforeachdb. Stop using that procedure, it is an unreliable pile of unsupported and undocumented crap that is known to skip databases in certain scenarios (usually where > 100 databases are used on a busy system).

Solution: write your own cursor with sensible options:

CREATE PROCEDURE dbo.my_own_foreachdb
  @command NVARCHAR(MAX)
AS
BEGIN
  SET NOCOUNT ON;

  DECLARE @db SYSNAME, @sql NVARCHAR(MAX);

  DECLARE c CURSOR 
    LOCAL FORWARD_ONLY STATIC READ_ONLY
    FOR SELECT name FROM sys.databases;

  OPEN c;

  FETCH NEXT FROM c INTO @db;

  WHILE @@FETCH_STATUS = 0
  BEGIN
    SET @sql = 'EXEC ' + QUOTENAME(@db) + '..sp_executesql @command';

    EXEC sp_executesql @sql, N'@command NVARCHAR(MAX)', @command;

    FETCH NEXT FROM c INTO @db;
  END

  CLOSE c;
  DEALLOCATE c;
END
GO

Sorry, untested, busy day over here - but should demonstrate the approach.

Or see this and this (I wrote a more reliable and flexible replacement).