Yes this can be done with the Rules module. Here is a summary of what you'll need to get it to work:
Keep track of all node IDs of a user that still need to be deleted later on (after the user upgrades). For this add an entity reference to the user's profile (multiple values allowed). And each time such a node get's authored (as in your question), you need to add the reference to that node as an extra value in this entity reference field (= Rule 1). So basically this is the "queue" of nodes for a user that need "post processing" after the user upgrades. It is will serve as your entry point starting from the user's id to "access (find) the exact node ids again later on".
Create a rules component (= Rule 2, though of type "component") with parameter just a "node id". All this Rules component has to do, is to "delete" the node indicated in the parameter. But you can add any Rules "Conditions" also if you'd need any (already now or later on if requirements change).
Create a rule (= Rule 3) containing a Loop that should be triggered after the user upgrades. The goal of this rule is to loop over each of the nodes in the reference field from Step 1, and in each iteration of that loop you use an action which is to invoke the Rule Component as detailed in Step 2 (and which uses the node id as a parameter).
If you're not familiar (enough/yet) with using Loops in rules, then watch the video about List and loops.
For a video that is fairly similar to what's needed in step 2 and step 3, refer to the 2nd video (= Solution video) about Creating multiple back links. Some more details about how your scenario slightly differs from what is shown in that solution video:
- You are creating an entity reference to nodes also, but from a user (not a node).
- You only need the first parameter (= Node to link to) in your Rules component (you don't need the 2nd parameter).
Easy, no? ... and no custom code involved.