Delete nodes using Rules and VBO
Here is an "educated" guess:


Your site is configured so that anonymous users are NOT allowed (= do not have the permission) to delete nodes.
Cron (always) runs with user anonymous.


Up to you to confirm if bullet "1." applies, but rest assured that bullet "2." is true (in any Drupal 7 site). So if "1." indeed applies, the answer to your question (= "What am I missing") is that to get this to work you need to grant delete of nodes to anonymous users. I bet it is not going to be what you want to do (I wouldn't ...), but trust me, that is what you're missing.

And BTW, it must be that the userid you used to "successfully manually delete the nodes with VBO" does have the required permission.

To verify if my guess makes sense: (temporary) grant access to the VBO view to anonymous users, logout from your site, and repeat your manual attempt to delete the nodes with that VBO view again (as anonymous user). I bet it will fail with some sort of permission issue. Turn on Rules debugging (within Rules sessings) to get more details about that via the Rules logging messages shown near the top of your screen).