I have had Veeam 365 running backing up my email address and a couple of shared mailboxes without issues for over a year when suddenly I started getting this error message. After googling for a while I didn’t find an answer to what would be causing it. I’m also on the community edition so no support, unfortunately!
The shared mailboxes were continuing to backup without issue but the one licenced mailbox in the tenant was having issues.
11/03/2022 11:00:32 :: Failed to retrieve licenses for 1 users
I could see that I have 0 licenses of 10 assigned in veeam so it seemed to be failing to actually assign it to a user.

After looking through the logs I found something interesting in Veeam.Archiver.Proxy Log
C:\ProgramData\Veeam\Backup365\Logs
It was reporting an access denied error while the job was running.
[11.03.2022 02:00:00] 9 (3452) Failed to send heartbeat to server
[11.03.2022 02:00:00] 9 (3452) Error: Access is denied.
[11.03.2022 02:00:00] 9 (3452) Type: System.ServiceModel.Security.SecurityAccessDeniedException
[11.03.2022 02:00:00] 9 (3452) Stack:
[11.03.2022 02:00:00] 9 (3452) Server stack trace:
[11.03.2022 02:00:00] 9 (3452) at System.ServiceModel.Channels.ServiceChannel.ThrowIfFaultUnderstood(Message reply, MessageFault fault, String action, MessageVersion version, FaultConverter faultConverter)
[11.03.2022 02:00:00] 9 (3452) at System.ServiceModel.Channels.ServiceChannel.HandleReply(ProxyOperationRuntime operation, ProxyRpc& rpc)
[11.03.2022 02:00:00] 9 (3452) at System.ServiceModel.Channels.ServiceChannel.Call(String action, Boolean oneway, ProxyOperationRuntime operation, Object[] ins, Object[] outs, TimeSpan timeout)
[11.03.2022 02:00:00] 9 (3452) at System.ServiceModel.Channels.ServiceChannelProxy.InvokeService(IMethodCallMessage methodCall, ProxyOperationRuntime operation)
[11.03.2022 02:00:00] 9 (3452) at System.ServiceModel.Channels.ServiceChannelProxy.Invoke(IMessage message)
[11.03.2022 02:00:00] 9 (3452) Exception rethrown at [0]:
[11.03.2022 02:00:00] 9 (3452) at System.Runtime.Remoting.Proxies.RealProxy.HandleReturnMessage(IMessage reqMsg, IMessage retMsg)
[11.03.2022 02:00:00] 9 (3452) at System.Runtime.Remoting.Proxies.RealProxy.PrivateInvoke(MessageData& msgData, Int32 type)
[11.03.2022 02:00:00] 9 (3452) at Veeam.Archiver.Interfaces.Services.IControllerCommonServices.GetVersion()
[11.03.2022 02:00:00] 9 (3452) at Veeam.Archiver.Engine.Extensions.PrimitiveServiceClientExtension.CheckControllerVersion[TChannel](PrimitiveServiceClient`1 client)
[11.03.2022 02:00:00] 9 (3452) at Veeam.Archiver.Engine.WcfService.Connection.ServiceConnectionBase`1.ConnectInternal(ServiceConnectionConfig config, Nullable`1 cancel, Nullable`1 openTimeout, Binding binding, ServiceEndpointAddress serviceEndpointAddress)
[11.03.2022 02:00:00] 9 (3452) at Veeam.Archiver.Engine.WcfService.Connection.ServiceConnectionBase`1.Connect(ServiceConnectionConfig config, Nullable`1 cancel, Nullable`1 openTimeout)
[11.03.2022 02:00:00] 9 (3452) at Veeam.Archiver.Engine.WcfService.Connection.ServiceConnectionBase`1.ConnectTo(IServiceConnectionConfig config, CancellationToken cancel, Nullable`1 openTimeout)
[11.03.2022 02:00:00] 9 (3452) at Veeam.Archiver.Proxy.Wcf.ProxyToControllerConnectionFactory.InitializeConnection(IServiceConnection connection, CancellationToken cancel, Nullable`1 openTimeout)
[11.03.2022 02:00:00] 9 (3452) at Veeam.Archiver.Proxy.Wcf.ProxyToControllerConnectionFactory.<>c__DisplayClass2_0`1.<Create>b__0(ServerClientConnection`1& connection)
[11.03.2022 02:00:00] 9 (3452) at Veeam.Core.Memory.Disposable.Create[TValue](CreateAction`1 createInstance)
[11.03.2022 02:00:00] 9 (3452) at Veeam.Archiver.Proxy.Wcf.ProxyToControllerConnectionFactory.Create[TChannel](CancellationToken cancellationToken, Nullable`1 openTimeout)
[11.03.2022 02:00:00] 9 (3452) at Veeam.Archiver.Proxy.ServerConnectionManager`1.CreateConnection(CancellationToken cancel, Nullable`1 openTimeout)
[11.03.2022 02:00:00] 9 (3452) at Veeam.Archiver.Proxy.ServerConnectionManager`1.GetConnection(CancellationToken cancel, Nullable`1 openTimeout)
[11.03.2022 02:00:00] 9 (3452) at Veeam.Archiver.Proxy.HeartbeatService.Run()
This was actually being caused by 2 issues.
First Issue (Self Caused)
One was caused by myself renaming the machine that it runs on so the Proxy was now pointing to the wrong location (the hostname did not resolve).
Under Backup Infrastructure > Backup Proxy’s
The default one was now pointing to the hostname of the VM from before the rename. It was easy to get around this I simply added the hostname to the host’s file so both the old and new would resolve to the VM and checked that the credential was working.
Actual Issue
I now got past the error connecting screen but was still getting error denied.
I checked I could browse to \hostname\admin$ and that was working fine.
I found after more digging that the Remote Registry service was disabled and not running. I turned this to automatic and started the service and tried the backup again and Success!

The license was assigned in Veeam 1 out of 10 now being used and the backup run without issues.
Hope this helps anyone having a similar issue.