What I've done in those situations is gently but firmly used my trusty handy-dandy turkey baster to send streams of water right at the base of his foot, to get him to let go... If you can get even the tiniest bit of the foot to come up, start sending water between his foot and the rock until he comes loose...
One BIG word of caution! Be VERY careful you don't have the end of the turkey baster near the anemone (Or anything else delicate) during the "intake" phase, or you'll suck his flesh in and cause some damage...
Another thing I've tried is to hold a piece of ice next to the foot, to get the initial "let off" so you can pry him off with water bursts after that...
