Problem uninstalling android application

From time to time I'm facing an application that refuses to uninstall using the market. Here is the procedure I'm using (if any step works - there's no need to continue):

1. Uninstall using the Android Market application
2. Uninstall using the settings menu from the home screen: 'Menu' -> 'Settings' -> 'Applications' -> 'Manage Applications' -> select the application & uninstall.
3. Uninstall using a 3rd party tool, for example: ASTRO file manager (in the application click 'Menu' -> 'Tools' -> 'Application Manager/Backup' -> long click the application -> 'Uninstall')
4. Reboot the phone and try steps 2 & 3 again.