Os eventos aos quais você está limitado no nível da planilha são os seguintes:
Activate
BeforeDoubleClick
BeforeRightClick
Calculate
Change
Deactivate
FollowHyperLink
PivotTableUpdate
SelectionChange
Suponho que você poderia tentar algo no evento SelectionChange. Se alguém alterar a formatação de uma célula e depois mudar para uma célula diferente, esse evento será chamado.
Qualquer que seja o código que você tenha nessa área será constantemente chamado, então seria uma boa idéia começar o que você fizer com algumas verificações rápidas para ter certeza de que as células estão em um determinado intervalo, dados, etc. ficar bastante lento, caso contrário, os usuários mudam de uma célula para outra.