I confirm contacts links are totally broken in frontend and language swicther too.
There are many errors. Looks like something fundamental has been modified in core.

replacing in
/components/com_contact/helpers/association.php
the top lines
by

defined('_JEXEC') or die;

//use Joomla\Component\Contact\Site\Helper\Route as ContactHelperRoute;
use Joomla\CMS\Factory;

JLoader::register('ContactHelper', JPATH_ADMINISTRATOR . '/components/com_contact/helpers/contact.php');
JLoader::register('ContactHelperRoute', JPATH_SITE . '/components/com_contact/helpers/route.php');
JLoader::register('CategoryHelperAssociation', JPATH_ADMINISTRATOR . '/components/com_categories/helpers/association.php');

will solve that issue.

Alas, we also have the "modern" routing issue here.
I.e. if we associate categories but do not create a All Contact Categories or a direct menu item to the associated category for each content language, the absence of an Itemid will not display the association.

I will make a patch which only can be temporary as I guess the use etc. should work in the future.

cc @laoneo Please look into this when you have a time.

Contacts is not migrated yet fully to services and namespaces as there are still open pr's (#20339, #20693 and optionally #20640) which need to get merged first. Then I will migrate contacts, banners, newsfeeds and categories. But leave this issue open till all is done and then we can come back to this one again. Till then there is no really a point in testing these extensions.

@laoneo thanks for Info.

@laoneo all three mentioned Pull Requests are merged, are "contacts, banners, newsfeeds and categories" also migrated and this one can be tested again if Issue still exist?

Yes

Thanks @laoneo. Issue is the same as described in first Comment.

I confirm the issue is still present. Tested for contacts although they rightfully use AssociationServiceInterface
The issue is present for SEF as well as no SEF.

I confirm the issue is still present.

@laoneo
can you look at this please?

I have retested this old issue and it is no longer reproducable (as expected) and can now be closed