My shop may be small, but I see a lot of similarity between keeping track of tools and keeping track of parts and I have a great amount of experience there. That experience has ranged from setting up storage for small, electronic and mechanical parts up to managing a facility that occupied a city block with everything from washers up to items that needed a forklift or crane to lift.
The main thing with storing parts is to have a system where you can go directly to a location for the part, the item you want. In order to do this you must go to one of two general ideas: the first is to store the items by some kind of logical system such as an OEM or generic part number or by a physical attribute (size, thread pitch, etc.) This type of storage is usually easier to set up and faster in use, but it also has some drawbacks. If you have a bin for a 1" widget next to a bin for a 2" widget, then when you get a 1.5" widget, you must move the 2" bin and all the larger bins down one space to make room for that new item if you are going to put it in the proper place. This takes time and effort and all too frequently, it is not done. So the 1.5" widget winds up on some, randum empty shelf.
The other way is to use the available locations but have a locator system for them. And then record the location of each new item as it is added to the collection either manually or electronically (computer file). Again this has good and bad points. You lose the ability to see your entire stock of a type of widget with a single glance at one shelf. But the use of the available storage space is a lot more efficient. And that system of recording the locations must be strictly maintained or items will be lost.
I have used both of these systems and both can work. But that usually means that one or more people must be dedicated to work with them, FULL TIME. And they are the only people who are allowed to store or retrieve anything. From my experience, the first system is better when even a single full time employee is not feasible. One or more people can straighten out any problems in their "spare time". One thing that I have done when setting up such a system is to leave empty spaces for new parts (tool sizes) at frequent internals. That, along with some kind of bin or other STANDARD container for each part (tool) makes it easier to keep everything in sequence. In my example above, instead of moving all the bins with widgets larger than the 1.5" size, only a few need to be moved, usually all on one shelf.
This can be done on more than one level. So I use cardboard bins for my shop stock of bolts and nuts. One bin for each size (diameter and thread pitch). So if I suddenly must store a fastener with a new (to my shop) pitch, I just add a bin for that one by moving the other bins down to make space. But I do not stop there. INSIDE each cardboard bin I have either screw top containers or smaller mini-bins for each type and length of screw/bolt/nut. And I can also make a space inside each bin by just moving those inner containers around. Of course, everything is labeled. Hence, each fastener has IT'S place and I can go to that place very quickly.
I have extended this to some of my cutting tools, like drill bits and milling cutters. Yes, I have several drill indexes where I keep most of the bits that are in use. But I buy drill bits in quantity to get better prices. And I have cardboard bins with various smaller storage devices inside those larger bins. And likewise for milling cutters: cardboard bins that are subdivided for the various types of cutters that I have.
How this applies to the OP's question as to how I keep track of where a cutter should be stored is simple. First, I go to the larger bin for that type of cutter. Then, within that overall bin there are smaller bins or other containers where each size/number of flutes/alloy/etc. cutter is stored. AND, within that smaller bin, in most cases I will have the OEM packages. I keep a marking pen handy and MARK the OEM package when a cutter is first used. That way, I both know where to return it to when my current task is finished AND I know which packages have new and which ones have used cutters.
This works for me. And it is fairly easy to keep up with. I must confess that some times I do bring the cutter to the mill in that OEM package. But returning it to the proper bin and inner bin is easy.