Το PHP mail δεν συστήνεται γιατί ουσιαστικά στέλνεις anonymous mails και υπάρχει μεγάλη πιθανότητα να θεωρηθεί ως spam. Συνιστάται η χρήση SMTP με authentication και SSL.

Πρέπει να διπλό-τσεκάρεις ότι οι ρυθμίσεις σου είναι σωστές. Αν είσαι ΟΚ, μην κοιτάς στο Elxis, το πρόβλημα θα είναι στο server, 100%. Ένα απλό που μπορείς να κάνεις είναι ένα ping στον mail server για να δεις κατ' αρχάς ότι είναι online. Μπορεί να μην είναι ακριβώς πρόβλημα, μπορεί να υπάρχει, πχ, κάποιος περιορισμός στο πόσα email μπορούν να σταλούν ανά Χ χρονικό διάστημα. Δεν ξέρω τι γίνεται στο server σου, μπορεί να έχει πάνω 500 site. Ένα debug ίσως έδειχνε τι ακριβώς συμβαίνει.

Δεν είναι φυσιολογικό να δουλεύει την μια και την άλλη να μην δουλεύει.

Θα χρειαστεί να επικοινωνήσεις με το πάροχο της φιλοξενίας του email λογαριασμού σου.
Να σου δώσει τις απαραίτητες πληροφορίες. Βάση μηνύματος κάτι έχει αλλαχθεί από εκεί:
Connection could not be established with host mail.ntchosting.com (check host settings and username)

Όταν κάνω αποστολή δοκιμαστικού mail από την διαχείριση μου βγαζει το παρακάτω:
"Connection could not be established with host mail.ntchosting.com (check host settings and username)"
το πρόβλημα το κατάλαβα όταν μου έκαναν παράπονα ότι στέλνουν μηνύματα από την σελίδα και δεν παίρνουν απάντηση.
Στην διαχείριση δεν έχω αλλάξει τίποτα εδώ και καιρό.

Παρακαλώ για την βοήθεία σας.

The Medium article is member-only, but an audio version (by the author) is available here: https://archive.org/details/Cory_Doctorow_Podcast_412