When I right click on the email address of a sender to select "look up
outlook contact" I started to get the error message:

Cannot perform the requested operation. The command selected is not valid
for this recipient.

When I click the Show Help button I read

This error usually occurs when you attempt to view the calendar for a user
who has one or more of the following issues:
Is not part of your domain.

Is not listed in the LDAP.

Is not a member of your Exchange Server.

Has not granted you the necessary permissions to view their calendar.

To avoid this error message, use the Open Calendar command only if the user
is using Exchange Server. If the user uses Exchange Server and you still
encounter an error message, ask the user for the appropriate permissions to
view their calendar. If they are not part of your network, you will
probably not gain access to their calendar.

For more information, see Microsoft Knowledge Based article 813603.

This happens for every sender, and did not happen before today.