Well, non-linearity could be a problem if you were to estimate the time left to shutdown, but then that would depend on average use as well, so I think it would be too rough to be useful. Also my battery graph charts don't have the shape you describe, and contrarily seem to decrease linearly from the very top. So a millivolt-based meter might be feasible to estimate charge level imho.
$ ./batterypercent.sh Tue Feb 8 13:06:49 GMT 2011 3.965V - 76.5% battery.charge_level.percentage = 94 (0x5e) (int) ~ $ ./batterypercent.sh Tue Feb 8 15:05:38 GMT 2011 3.971V - 77.1% battery.charge_level.percentage = 77 (0x4d) (int)