A friend of mine expressed the problem described here in a more formal manner in this paper: http://gittup.org/tup/build_system_rules_and_algorithms.pdf

He ended up creating his own build system, "tup" < http://gittup.org/tup/ >, based off of it. It also has the property desired in this article that, "No-op builds should be O(1) and instantaneous, and most other builds should be O(WhateverChanged)".