Hi -
I had a very similar issue. I was seeing machines listed in the Security Status report under Scan Failures (never been scanned), but if you looked at the client itself, or even in the scan log from SEPM, it was clearly being scanned on our weekly schedule. I saw a similar issue with some machines related to AV definitions being out of date. They were flagged in the Security Status "Attention Needed" report, but if you checked the client (or the SEPM logs), you would see they had the correct defs.
This is due to duplicate entries in the database. Symantec provided me a tool that removed duplicate entries from my database. If found / deleted 385 entries, and after that my report was clean.
NOTE: I am running MR4 MP2 on the SEPMs. This problem did not affect all my clients. Just a very small number of them.
Symantec has confirmed to me that this is a known issue slated to be fixed in RU5.
I am keeping my fingers crossed for the real fix in RU5 (which is due in the next few weeks).
Doug