This is not much of an answer but it would not fit in the comment window;
You can do this with ArcObjects. I made a tool into which I enter parameters (extent, x and Y spacing) and it will create the grid in a existing polyline feature class. It's not too coplex to do this with ArcObjects but do create something like this does require a solid understanding of ArcObjects and VS.Net programming concepts. To do this dynamically for changing scales and to control labeling with ArcObjects would be a fairly complex add-in. (controlling dynamic labels programatically is difficult, at least I found it so) I only do a little bit of python mostly for geoprocessing for which it is primarily intended but I am pretty sure this cannot be done with python. Take this last statement with a grain of salt because I have not yet downloaded version 10.1 and I believe Python functionality has been extended in the new version. With ArcObjects however you can, among other things, control every aspect of the ArcMap framework which also allows you capture the extent of the layout extent and transform it real world coordinates and vice versa.
My add-in is a lot simpler then what you are looking for but it would be a good start. As I mentioned it creates the grid in a feature class based on the parameters you enter. It optionally stores coordinates as attributes and I then use maplex for labeling. Maplex has enough options to let me control where the grid labels should appear but then again I only do this in documents with a set extent.
If you'd like I can post the Add-in. If you want to improve it I will also post the source code.