It may act like it uninstalled. It even goes through the complete uninstall routine. But unless you did it when it was thawed (with the red X blinking on the system tray icon), as soon as you reboot, voila, guess who came to dinner?

Deep Freeze must be in thawed mode to be uninstalled. Then you need to restart your computer again and it will be truly gone.