Is your grid a raster, a fishnet (line feature class), a polygon feature class, ..?
Will these new IDs for your points restart from 1 within each grid cell or do you want them to be globally unique (like a "3.7" where 3 would be the cell OID and 7 would be a point internal ID)?
I attached to this post a simple Python code that does the job based on an intersection between a point feature class and a polygon feature class (the grid. If you have a fishnet, you can convert it first into a polygon feature class.). The output of the intersection is a point feature class with at least one additional field that is the OID of the grid cell in which the point lies, for each point. The code loops then on the features/points of the intersection sorted by grid cell OID and generates new IDs, internal to each cell.
This would be one solution. It is not really smart and a little cumbersome if you never used Python scripting I guess, because I am not an experienced GIS user and I tend to program a little too much what could be done directly in one or two smart operations (without programming) by more experienced users. It should be for example possible to do it using the field calculator and an (advanced) expression using a static variable and the grid cell OID, but I didn't have time to investigate.
Cheers,
Cedric