Instead of trying to make brute force more costly, couldn't these services make it impossible, by forcing the fulfilment of a CAPTCHA when trying to expand/follow a shortened URL?