More than 5 years!
Actually, MMS has been with us as long as camera phones, well over 7 years. Orange launched their service for 2G users in 2002 and the I had both an Orange GD87 and a 3G NEC e606 on "3" with MMS in 2003. I think your right in that 2004 was the year just about everyone seemed to have it though.
It's funny though, MMS seems to have died off in the last year or so. The current trend seems to be to bluetooth pictures/video/music phone to phone - I suspect due to the MMS size limitations.
I wonder when the iPhone will get that ability?