You wouldn't want to use MD5 specifically because it would take up 32 characters of your message, but a simpler checksum might work.
laumars
MD5 was more a proof of concept than a design specification. However 32 characters is only 1/5 of an SMS so it's not beyond the realms of a practical (albeit lazy) fix.
Ideally though, you'd be right that something more concise would be preferable.