Is it legal to use rented dedicated servers to mine?
It's definitely not against the law. It might be breaking the terms of service (ToS) but there's really no reason why any dedicated server hosting provider wouldn't allow you to max out the CPU. I wouldn't do business with them if they limited that. However, you need to read your hosting provider's ToS. They might forbid certain applications like IRC servers, BitTorrent, Tor, etc. If they don't list Bitcoin then you are good to go.