To maximize, it seems like at least you'd want to associate negation with:
- independent words
- conjugation/declension
- your loudest phonemes
- distinct word order
- distinct prosody
You could have a number of independent markers/words as mentioned above.
Turkish has verbs which always negate, and Turkish verbs usually end the thought: e.g., 'değil' for "is not [noun or adjective]"; 'yok' for 'there is not [something].' For negating verbs, it has an infix as part of the conjugation. Reflecting back your point about 'can't,' as a non-native speaker, I can miss this negative infix sometimes. This, even though it is higher on the sonority hierarchy (easier to hear) than the plosive T you point out in 'can't.' (It uses M and a variable vowel.)
So, if you wanted to change a conjugation to express "not," say, instead of a T or even an M, you could try using the loudest sounds in your set (usually wide-mouthed vowels?), ha ha.
You could change word order for negated sentences. We do that for questions. I have noticed. Have you noticed? [rhetorical ;) ]
Also, you could reserve a certain, unusual tone, pitch, stress pattern, etc., for negating, like how it's pretty easy to hear the lilt we put at the end of a question? Not that this is exclusive of the other options, but imagine to say, "You can't have a muffin," you deepen your voice as much as you can and borderline-sing, "You can have a muffin." If people associated deep voice with negation like we associate that rising tone with questions, that'd be pretty hard to miss.