My company's written policy is for everything to be locked out and tagged out before working on a piece of equipment. No one is permitted to work on anything energized. Will we still need to do an arc flash hazard analysis or will generic labels be enough?

What does your generic label say about PPE? Will you know what PPE to wear when verifying deenergization?

It's not locked out until it has been verified as de-energized, and proper PPE is required for voltage testing (even testing for the absence of voltage).

Also, what about troubleshooting?

This is a common claim. We don't do ANY live work but the two above examples are common everywhere. You must deal with these. Another common mistake is that we do not allow work >40 cal when you have hazards >40 cal you will allow some type of "work" in the form of testing or grounding or both.

The above examples are good. In addition, you cannot tell what situations will come up in the future, or how things will change, or what mistakes people will make. So NFPA 70E does not saying labeling is required, except... (There is no "except.") The bottom line is that correct, accurate labeling is required.