You might want to scan your system using Ad-aware SE to see if it'll find any tracking module too.
I just look-up at Spybot S&D and Rogueremover's pro database but they don't will not detect regcure and paretologic. Still, you might want to scan using Spybot S&D for I don't know what is the name of the tracking modules that Ashampoo found in your system.
You should also scan using Housecall:
Related info: The company behind Regcure is paretologic which offers an ex-rogue product, Xoftspy http://www.spywarewarrior.com/rogue_anti-spyware.htm#xos_note but note again that it is ex-rogue which means the xoftspy and the company is OK now but it's up to the user to take stuff from them or not.
I don't know why a registry cleaner requires internet connection (unless it has updater function that will check for updates?). Good move in blocking the connection to the internet. I use RegSupreme Pro by macecraft.com and it does not require internet connection. I have free registry cleaner too and they also don't require internet connection.