Στις 31 Μαρτίου 1959 ο Καζαντζίδης μπήκε στο στούντιο της Columbia για να ηχογραφήσει την "Συννεφιασμένη Κυριακή".
Το τραγούδι είχε ερμηνεύσει σε πρώτη εκτέλεση το 1948 ο Πρόδρομος Τσαουσάκης, το πρότυπο του Στέλιου στα πρώτα του βήματα.
Η πρόκληση λοιπόν ήταν διπλή.Η ηχογράφηση αυτή αποτέλεσε το αποκορύφωμα της συνεργασίας του με τον Τσιτσάνη που απέφερε 14 μοναδικά ζεμπέκικα.
Τον Καζαντζίδη πλαισίωσαν στα σιγόντα η Γιώτα Λύδια και η Μαρινέλλα. Επιστρατεύτηκαν επίσης τρεις κορυφαίοι εκτελεστές του μπουζουκιού και αναφερόμαστε βέβαια στον Κώστα Παπαδόπουλο, τον Λάκη Καρνέζη και τον Στέλιο Μακρυδάκη.
Παρέμενε ωστόσο για χρόνια άγνωστο ποιος έπαιξε την διάσημη πλέον προεισαγωγή. Το ταξίμι αυτό ακούγεται πρώτη φορά σε εκείνη την ιστορική ηχογράφηση κι έγινε για χρόνια το ραδιοφωνικό σήμα της Columbia - ένα μουσικό φετίχ για τους λάτρεις της λαϊκής μουσικής.
Κάποια στιγμή ο Κώστας Παπαδόπουλος σε μια συνέντευξή του διεκδίκησε ανοιχτά την πατρότητα του αυτοσχεδιασμού αυτού.
Ωστόσο την ιστορική αλήθεια αποκατέστησε ο επί χρόνια συνεργάτης του Λάκης Καρνέζης, περιγράφοντας με παραστατικό τρόπο τη σκηνή της ηχογράφησης.
Σε συνέντευξή του στο ηλεκτρονικό περιοδικό "Η κλίκα" αναφέρει επί λέξει: "Στη Συννεφιασμένη Κυριακή παίζει ο Τσιτσάνης, κάνει το ταξίμι μπροστά, αυτό που το έχει και σήμα η Columbia και μετά στην εισαγωγή μπαίνουμε εγώ ο Κώστας και ο Μακρυδάκης. Τρία μπουζούκια. Και τραγουδάει ο Καζαντζίδης. Αυτή είναι η εικόνα που έχω από το στούντιο που τη θυμάμαι ακόμα".
