Transaction log backup fails when one or more databases in the plan are set to SIMPLE recovery. The following useless error will appear in the job history:

Executed as user: {SOME}\{USER}. sqlmaint.exe failed. [SQLSTATE 42000] (Error 22029). The step failed.

The follow script will return a list of all databases that are currently set to SIMPLE recovery AND in one or more transaction log backup sqlmaint plans:

/*******************************************************
* Returns a list of databases that are set in one or
* more sqlmaint jobs that perform a tran log backup
* yet are set to SIMPLE recovery (READ AS A WAY TO FIND
* OUT WHY SQLMAINT is failing)
*******************************************************/
CREATE TABLE #tmp_tran_backup (dbname sysname)

-- List of databases that are are tran backed up
-- but are in SIMPLE recovery
INSERT INTO #tmp_tran_backup
SELECT [database_name] 
FROM msdb..sysdbmaintplans a
	INNER JOIN msdb..sysdbmaintplan_databases b ON
		a.plan_id = b.plan_id
WHERE a.plan_id IN (SELECT c.plan_id	-- Jobs that backup the log
			FROM msdb..sysdbmaintplan_jobs c
				INNER JOIN msdb..sysjobs d ON
					c.job_id = d.job_id
				INNER JOIN msdb..sysjobsteps e ON
					d.job_id = e.job_id
			WHERE e.command LIKE '%-BkUpLog%')
DECLARE @all sysname
SELECT @all = dbname FROM #tmp_tran_backup
WHERE dbname IN ('All User Databases','All System Databases', 'All Databases')

IF (@all IS NOT NULL)
	BEGIN
	TRUNCATE TABLE #tmp_tran_backup

	INSERT INTO #tmp_tran_backup
	SELECT name
	FROM master..sysdatabases
	WHERE 	(@all = 'All Databases')
		OR
		(@all = 'All System Databases'
			AND name IN ('master','model','msdb','tempdb','replication'))
		OR
		(@all = 'All User Databases'
			AND name NOT IN('master','model','msdb','tempdb','replication'))
	END

SELECT dbname, DATABASEPROPERTYEX(dbname,'RECOVERY') AS recovery
FROM #tmp_tran_backup
WHERE DATABASEPROPERTYEX(dbname,'RECOVERY') = 'SIMPLE'

DROP TABLE #tmp_tran_backup

Normal database backup fails when one or more databases in the plan that no longer exist (eg. they have been dropped/renamed). The following query will delete all entries from all plans for databases that no longer exist:

DELETE FROM msdb..sysdbmaintplan_databases
WHERE database_name NOT IN (SELECT name FROM master..sysdatabases)
	AND database_name NOT IN ('All Databases','All User Databases','All System Databases')