Sorry to hear that..That sounds terrible..Usually I check my links twice a month..Once I find that they've removed my links,I contact them instantly .. Fortunately I haven't found any one has removed my links without any notification..
Yes, I've had similiar problems, especially with link exchanges. You start the link exchange, they link back for a month or so and take away your link. Not very good business tactics at all.
Wow that's bad! I am definetely keeping an eye on this thread to see how it goes... I've heard, although not experienced yet, luckily, about: links removed links moved to deeper or less prominent position than agreed links altered so not clickable (but that look like they still are) links transformed to redirects links added (more than promised and diluting the strength) links with image instead of actual anchor text links with no follow added and there's more, some of which I won't even dare to say, in case it inspires someone... reputation is everything I think when dealing with someone over the net and luckily within a community such as dp's, there's a way of finding out, or at least an idea, good enough for small transactions. Beware!