How to "flag" product that had already been purchased before "flaging feature" was added?
If you can think of a way to create a view which contains 1 row for each product and the user who actually bought such product, and which wasn't flagged with this "already purchased" flag, then you can use such view as part of an actual solution for your question. In that case, you could get this to work by using the integration of VBO with the Rules module, as further detailed below.

Step 1: Create a Rules Component

Create a (rather basic) Rules component to flag a product by a user. Here is a variation of such component in Rules Export format (which processes nodes instead of products):

{ "rules_flag_node_by_a_user" : {
    "LABEL" : "Flag node by a user",
    "PLUGIN" : "rule",
    "OWNER" : "rules",
    "REQUIRES" : [ "flag", "rules" ],
    "USES VARIABLES" : {
      "flagging_user" : { "label" : "Flagging user", "type" : "user" },
      "flagged_node" : { "label" : "Node to be flagged", "type" : "node" }
    },
    "DO" : [
      { "flag_flagnode" : {
          "flag" : "your_flag",
          "node" : [ "flagged-node" ],
          "flagging_user" : [ "flagging_user" ],
          "permission_check" : "1"
        }
      },
      { "drupal_message" : { "message" : "Node flagged for user  [flagging-user:name] (uid=[flagging-user:uid])" } }
    ]
  }
}


This Rules Component uses a flag with machine name your_flag. After you edit that machine name to fit the name of your flag, you should be able to import this rule in your own site (using the Rules UI, which needs to be enabled). You can then adapt (or clone) it to make it work for your products instead of for nodes.

BTW: the Rules Action to display a message is just to see it at work while QA-testing this rule, feel free to remove that if you want.

Step 2: Let VBO do the work

This step is pretty easy ... Just build an appropriate view (of all products that still need to be flagged) and transform it in a VBO view. The clue to what you want VBO to do as an operation is ... Execute the Rules Component from Step 1. Be aware: when creating that VBO view, you really need
to create a view to "List Commerce Products".

If your Rules Component (= variation of the one in Step 1, where you flag products instead of nodes) cannot be selected as the VBO-action to be performed, then it might be because you need to change the order of the parameters used by the Rules Component: make the flagged_node (or flagged_product in your case) the very first parameter. This might be needed because it's a Rules Component with several parameters, and only the first one will be auto-populated by VBO. That might help to be able to select that Rules Component as your VBO action.

If you're not familiar with how to use VBO, have a look at the video about Using Rules components with VBO". If you want even more, then also watch the subsequent "Using Rules components with more than one parameter" video.

Attention: to process like 100.000 records at once is quite a challenge (memory requirements, etc). Therefor you might want to also watch the video about "More details about VBO settings" ... Before you are tempted to use VBO for processing them all at once ...

Video tutorials

If you're not familiar (enough/yet) with Rules, checkout the 32 (!!!) great, and free, video tutorials Learn the Rules framework.

Happy VBO-ing while Rules-ing!