Assuming we're limiting this to 5.56 brass, the NATO cross first appeared in the 80s when NATO officially standardized the first 5.56mm round, which was a load with the SS-109 bullet (the US version of this load is M855).  Until the mid-90s, M193 was loaded in brass without the NATO stamp, as M193 was never adopted as a NATO load.

As more and more units converted to 1:7-twist rifles and got rid of their 1:12s, the amount of M193 production shrank to the point where it was no longer economical to make a separate run of brass for M193, and so now M193 is loaded using M855 brass, NATO headstamp and all.

-Troy