Odd; did you do a 'yum clean all' each time as well?
Basically you have to remove the SW AND remove the entries in the rpm DB (which underlies yum).
you can also try
rpm -qa|grep -i wine
rpm -e <wine rpms mentioned above>
drastic but effective & do another 'yum clean all' afterwards before re-installing or 'updating'.
You could also do this immediately after the 'rpm -e ...'