It's taking quite long in gmusicbrowser to check all the music files, but in gtkpod (program that makes you able to sync your iPod in linux) checking is almost instant. The people at gtkpod have been very helpful to me so far, so you could probably ask them how they do it. Even though it's written in C, you could probably borrow the idea.

Well I don't know how they do it, but there is no magic :)
Other than watching the folders (which is more or less planned, but doesn't work anyway when gmb is not running), the only traces of the changes are the modification stamp on files and folders. The problem is that the changes are not recursive (changing a file's timestamp doesn't propagate to the folder and its parents), so you still have to check every file's timestamp to know if one file has been modified.
Coincidently, I recently stumbled upon this amarok blog post : http://jefferai.org/2010/01/rescanning-single-folders/ that explain how amarok does it, and its limitation. I guess that's how gtkpod does it too. But I'm not convinced that it's better. Maybe I could propose both modes ? (that implies saving all the folders timestamps :()

Ah ok, I get it.

I'm happy the way how it currently works, but maybe some users with huge media libraries don't want to wait for a long time to wait for the scanning to complete. So for them it could be quite useful. So maybe you could add support for both methods later indeed. But just focus on more important stuff first :)