이건 mysql일지 php일지는 모르겠지만.

손실되는게 맞고요 100% 복호화는 불가능합니다.
'int 32를 리턴' 하는 것이 아니라 32글자의 0-9a-f 를 return 하니까
string으로 저장하지 않고 hex binary로 저장하면 16바이트에 저장가능하죠.
(저는 그냥 string으로 저장해서 쓰는 편입니다만)

md5는 워낙 많이 쓰는 알고리즘이다 보니
자주쓰는 단어를 (Dictionary라고하죠) 미리 다 돌려놓고
결과값을 보고 원본을 찾아내는 경우가 많습니다.

위에 있는 md5 crack 링크들 다 그런 것이고요.

그래서 이를 방지하기 위해 앞뒤로 글자를 섞는 방법을 많이 쓰는데
( salt를 섞는 다라고 표현하기도 하고요)
function my_md5($str) {
return md5('이건사전에없겠지!@#!@#!@'.$str.'불안하니까뒤에도붙이나');
}

이런식으로 쓰면 dictionary로는 뚫을 수 없게 됩니다.

이렇게 긴 salt 정도 섞어주면 별 문제는 없는데요

2005년에 중국에서요.
md5 HASH 충돌을 일으키는 방법에 대해 발표된 자료가 있고요.

두 개의 다른 데이터를 가지고 같은 md5 결과가 나오도록해서
hash 충돌에 대해서는 진척이 꽤 많이 되있는 걸로 알고있습니다.

md5 string을 보고 원본을 복호화가 가능하단 소리는 아니고요.

이런 링크들 보시면 좋을것같네요
http://www.links.org/?p=6

ㅎㅎ