That reminds me, there was one phrase he said upon entering a level in SMS that I couldn't for the life of me comprehend. I know I heard one of his phrases was "arriva derci" but I don't think this was it. Anyone have any ideas?
The Chef: I have found your answer (and you were actually extremely close!).
Here's an excerpt taken from mariowiki.com
"In Super Mario Sunshine and Super Mario Galaxy, the 'Too Bad!' changes into a red Game Over sign. In translated versions of Super Mario Sunshine, it says 'arriverderci', Italian for 'goodbye'."
Mario says that word sometimes when he dies, and like you said you've heard, I've heard it too.