a) Wenn das STK500 als Programmiertool genutzt wird, gibt es da den Jumper für die externe Versorgung (VTG / JP2 ?? - schau mal ins Handbuch, ich bin wegen der Namen nicht sicher). Zu Deiner ISP-Schnittstelle passend muß der hier gebrückt (gesteckt) sein und die STK500-Spannung natürlich auch auf 5V stehen. Dann geht das auch.
noch hinzuzufügen wäre, dass die Pegel recht sauber aussahen, da meine erste Vermutung war, dass die irgendwie verschliffen wurden
Okay, wenn die Signale alle sauber kommen, dann ist das wohl nicht der Grund.

b) Der Programmiertakt darf maximal ein viertel der AVR-Taktfrequenz betragen, ein fabrikneuer AVR läuft auf internem RC-Oszi mit etwa 1MHz, oder?
Meist wirkt es, den ISP-Takt auf den niedrigsten verfügbaren Wert zu stellen, und erstmal die Fuses für den Oszi richtig zu setzen. Danach kannst Du dann den ISP-Takt auf den besten Wert hochdrehen, sonst dauert das Flashen so ewig.