I found the problem. Seems the code generated by SQL Server isn't working in the maintenance plan, though it works fine when I run that code manually:

USE [MYDATABASE]

GO

DBCC CHECKDB WITH...

Part of the maintenance plan is working, because the backups are running fine. And the log says that the integrity check is succeeding as well, which is why it's odd....

I'm having a similar problem. Check DB Integrity is part of my maintenance plan, but it returns no errors and the logs say it runs very quickly (around 15 seconds...

Thanks for the good advice! I think I'll go with Michael Earl's suggestion, since that would work nicely for my needs.