Chiming in to say that
GraphicsGale (free edition) is an excellent tool for making pixel art. I'd even go so far as to say that the only thing that Paint has on it is the ability to work with bigger pencil sizes (which, depending on how you work, could be a major flaw, but fortunately i work with lines rather than blotches of colour). Basically, it shows you where the pixel will be placed before you click, which is a TREMENDOUS help, and also picks colours ala pipette with the right mouse button, something i'm sorely missing in Paint. Also, it has that grid you're seeking as well, which i suppose is another point for it.
It also has a small preview window within it, which can be very useful indeed, since it saves you the trouble of zooming out all the time by means of displaying a full-scale view of the sprite/area (depending on size) you're working on.
tl;dr
screenshot of all the neat things. Note that the singular free black pixel you see is just where my cursor was, it's not placed yet. I typically don't work with a grid, but i enabled it just to show that it's there. (in case you try it: View --> Grid)
GraphicsGale is specifically made for spriting/pixel art, so it's no wonder that it's pretty good for the purpose.