Okay, so I did a bit of digging, and perhaps found a clue as to why the option is not accessible (to some at least). Read this MacWorld Hint, specifically, look down at the comment from joekewe (on Feb 08, '11 06:08:14PM):
From a web search, it looks like "Verify Time Machine Backup" should be called "Verify Time Capsule" backup. My system log shows that I attempted to verify my Time Machine backup:
com.apple.backupd[70595]: Backup verification requested by user.
but (I believe) because it is a locally mounted volume, it didn't do anything and didn't leave any more entries in the log. From this older knowledgeable article, it looks like Verify Time Machine was added when Time Capsule was having trouble.
It might be the case that he's onto something. The option is also grayed out for me, but I have a local TM disk connected via USB. Can anyone confirm they can use the feature with their Time Capsules?
It may have been that they actually fixed the menu option, in that, it should have been grayed out for Snow Leopard users connected through USB (read the comments as many people talk about having the service do nothing), but it wasn't. So in Lion, it behaves correctly.