as the underlying assumption of encryption on the part of the service provider. If someone in Internet land is storing passwords in an unsecure fashion then a backend harvest will net them your password no matter how strong it is. In those cases about the only thing you have control of on the front end is password rotation frequency/differentiation.
Otherwise I agree completely with what you are saying, esp wrt padding. Make a password rule too complex and you can usually find it on a post-it-note.
Keep Up with TechRepublic