The uninstall process will be different for different applications, just like in windows. Some apps leave stuff behind and that can be useful if you are upgrading to a paid app after trialling a free version or re-installing when you're having problems and don't want to lose all your settings, game saves or other data .
Afaik, the only way to guarantee a clean uninstall is factory reset, but then you'll lose everything. Plus it may not fix the problem. Android 4.0 is fairly new. Most apps were written for 3.2 or earlier and may not work properly with 4.0. just like WinXP programs may not run properly or at all with Win7.
That is the reason I have held off updating to 4.0. Honeycomb 3,2.1 works OK for me and there's nothing in 4.0 that is going to change my world. It might be a bit faster and slicker but the trade off is the risk of incompatibility with existing apps.