Right there with you. I've dealt with the dreaded overflowed by XX bytes message more then I'd like to remember.
I've also run into the issue where you tell the business hey, this isn't going to reach QA for another 2-3 weeks now. And when you explain the details that we are 20 bytes over memory (etc) and need to make space they think of it like removing some characters in a sentence on a word document, not understanding it might take reorganizing an entire module or 2 or rewriting entire state machines or whatever it takes.
And yea, the deals thing is funny cause it seems to happen in every embedded system where multiple people are involved on the project.
I'll laugh with you but not at you. It is a blast to do embedded work