I think that's because the icon is part of the package -- if you right-click on TextMate and choose 'show package contents' it's in there under Resources. I'd be interested in knowing how to make my icon choice permanent too if someone else knows. Is there a system repository?
No the system looks for the icon in application resources, no way to make it permanent. There is a cache that can make the change lag behind an update, but it would update eventually.