I think that the over-optimization term should be forgotten now. It was a casual remark made by Matt Cutts which has since been clarified. There is no "over-optimization", there is optimization and there is spamming.
Anyway, what the OP was asking was not what not to do, but which off-page activities would be effective now. Do you have any positive suggestions that would help answer the question please?