I have a validation rule on the Billing Address which I want to work only on Accounts. Howveer this rule is being applied to the address on Leads and Contacts also.
Can you post the rule? Your Account validation rule could be applied in the Lead conversion process if you've got Leads set to enforce validation rules. Otherwise, it should only be enforced on edits to the Account record.
