Maintenance plan fails on non-existent database
In order to identify where this is coming from (because who knows which step in your maintenance plan is actually tripping on this), I recommend running the following tedious code, which will identify views that show the database name even if it is a database that no longer exists in sys.databases (dropped, renamed, what have you):

DECLARE @db SYSNAME = N'RollbackSnapshotTempDB{12345678-1234-1234-5678-012345678912}';

DECLARE @sql NVARCHAR(MAX) = N'SELECT N''--''';

SELECT @sql += N'
 UNION ALL SELECT TOP (1) ''SELECT * FROM msdb.' 
   + QUOTENAME(s.name) + '.' + QUOTENAME(o.name) + '
   WHERE ' + QUOTENAME(c.name) + ' = '''''' + @db + '''''';''
 FROM msdb.' + QUOTENAME(s.name) + '.' + QUOTENAME(o.name)
 + ' WHERE ' + QUOTENAME(c.name) + ' = @db'
 FROM msdb.sys.all_objects AS o
 INNER JOIN msdb.sys.schemas AS s
 ON o.[schema_id] = s.[schema_id]
 INNER JOIN msdb.sys.all_columns AS c
 ON c.[object_id] = o.[object_id]
 WHERE c.name IN (N'database_name',N'dbname',N'db_name',N'Database Name')
 AND o.type IN (N'U',N'V');

SELECT @sql += N'
 UNION ALL SELECT TOP (1) ''SELECT * FROM master.' 
   + QUOTENAME(s.name) + '.' + QUOTENAME(o.name) + '
   WHERE ' + QUOTENAME(c.name) + ' = '''''' + @db + '''''';''
 FROM master.' + QUOTENAME(s.name) + '.' + QUOTENAME(o.name)
 + ' WHERE ' + QUOTENAME(c.name) + ' = @db'
 FROM [master].sys.all_objects AS o
 INNER JOIN [master].sys.schemas AS s
 ON o.[schema_id] = s.[schema_id]
 INNER JOIN [master].sys.all_columns AS c
 ON c.[object_id] = o.[object_id]
 WHERE c.name IN (N'database_name',N'dbname',N'db_name',N'Database Name')
 AND o.type IN (N'U',N'V');

SELECT @sql;

EXEC sys.sp_executesql @sql, N'@db SYSNAME', @db;


This should produce output in the bottom pane like this (hopefully only a few rows):

--
SELECT * FROM msdb.[dbo].[backupset]
  WHERE [database_name] = 'RollbackSnapshotTempDB{12345678-1234-1234-5678-012345678912}';


You can copy and paste that output into the top pane and run it, and then act accordingly. For rows you find in backupset, for example, you can just delete them. If they are in catalog views this may be a little tougher - tell us what you find and we should be able to figure out how to fix it. 

(Also, this isn't exhaustive, there are likely other places a database name might be stored using other variations on the name column. By design, I'm avoiding the obvious places like sys.databases.name, because you claim you've already checked there.)

Now, I would recommend Ola Hallengren's free maintenance scripts or even paid solutions like SQL Sentry Fragmentation Manager* for various types of maintenance, over the cumbersome and buggy native maintenance plans. 

Short of that, stop using "all user databases" since this seems to cover more than just the set of databases that are currently present. I'll be interested to hear if you find this database name in any of the catalog views, backup-related, or job-related tables. I also have a tip publishing soon about searching all string columns across all databases on an instance, and it might be even more productive than the targeted script I wrote above. I'll try to remember to come back here and update this post with a link once it has been released.


Disclaimer: I work for SQL Sentry.