I have read that they used previously breached machines, but to try to gain access to those machines they also needed some kind of protection right? How did they do it then?
The answer is quite un-exciting: they didn't need to do anything.
You are talking about a time when there were not a lot of cyber laws and fewer people who could understand or enforce them. So law enforcement only spent their resources on the big crimes.
So, if someone wanted to commit a big crime, they would do what you mention: take over a smaller company/service, wipe the logs (no one would notice), then use that as a launchpad. If they were discovered on the smaller location, they would not have committed a crime big enough to warrant investigation. So, they could do it over and over again as much as they needed to.
No need to get fancy with your "detection evasion techniques" when there is no one watching.
In the late 1990's, remote administration of UNIX based systems was done almost entirely by telnet and HTTPS was just beginning to gain traction. This should tell you a lot about the security posture of the time.
- Unauthenticated SOCKS proxies were available in the thousands. Scanning port 1080 across the internet to find them was trivial.
- There were free shell services from a bunch of different providers who didn't know who was using them.
- Free dialup subscriptions that didn't adequately require user identification were getting mailed to everyone in my country.
- Huge numbers of routers had guest account access with standard passwords for other admins to troubleshoot network issues. These accounts could be used to initiate connections and often had no command logging. Cisco guest:guest comes to mind.
- Standard default passwords on computer systems were widespread and easy to scan for. IRIX lp:lp comes to mind.
- Open access from universities and public libraries was becoming standard without any identification required.
- Email accounts which came with shell access were being issued to entire student bodies with a single default password for all. Account username lists being printed and posted on a wall was not uncommon.
- Wardialing for modem banks that could be used to bounce a connection was still effective.
The list goes on and on, but these were some of the more common techniques I heard about. Several well known BBSes would trade lists of phone numbers, IP addresses or credentials for any of the issues listed above. Security and evidence preservation were really not widespread concerns in that era. As described by schroeder's answer, enforcement was further encumbered by lacking precedent, rare forensic know-how and juries simply not comprehending the subject.