Exchange web service (EWS) Gives Internal server error in the middel of successful FindFolder response

I'm making a Office Add-in in Javascript, and I suddenly gets an Internal Server Error xml document in the middle of the successful soap response document.

This used to work but I'm currently getting the response with a new failure xml document in the middel. See FolderId Id=" and then a new xml document stars.
I have never seen this before. Does anyone have any idea of what is wrong, or how this can be diagnosed?
The response has been snipped a bit to be easier to read and apparently the namespace links causes the post to be marked as spam.

<?xml version="1.0" encoding="utf-8"?>
<s:Envelope>
...
		<s:Body>
			<m:FindFolderResponse>
				<m:ResponseMessages>
					<m:FindFolderResponseMessage ResponseClass="Success">
						<m:ResponseCode>NoError</m:ResponseCode>
						<m:RootFolder TotalItemsInView="1" IncludesLastItemInRange="true">
							<t:Folders>
								<t:Folder>
									<t:FolderId Id="
										<?xml version="1.0" encoding="utf-8"?>
										<s:Envelope>
											<s:Header>
												<Action s:mustUnderstand="1">*</Action>
											</s:Header>
											<s:Body>
												<s:Fault>
													<faultcode
														xmlns:a="http://schemas.microsoft.com/exchange/services/2006/types">a:ErrorInternalServerError
													</faultcode>
													<faultstring xml:lang="en-US">An internal server error occurred. The operation failed.</faultstring>

I'm calling EWS like this:

const req = "...SOAP Request XML...";

Office.context.mailbox.makeEwsRequestAsync(req, (asyncResult) => { 
   logger.log("FindFolder: " + asyncResult.value);
});

The Exchange server is Office 365.
The folder list I'm trying to get is a list of public folders, and it worked a few days ago. I have moved a few folders around, and got this after the move. I have since deleted all folders and tested, created new folders and tested. Everytime the same error. Depending on how many folders is returned the error breaks off the response in different places.

(Sorry, I can't comment only place an answer!)

We've also found this problem started occurring in the last few days. We've found the same problem happening when using the EWS Managed API. In summary, this looks like a problem on the EWS end. From what I can tell, this looks like a genuine problem rather than just a change in behaviour.

GitHub EWS Managed API thread about this issue: https://github.com/OfficeDev/ews-managed-api/issues/294

And I have posted about it on Microsoft Q&A here: https://learn.microsoft.com/en-us/answers/questions/1229639/exchange-web-services-ews-findfolders-produces-a-5

We have same problem.
I attach listener to the EWS and the error happeens in GetFolder, FindItems etc in case if we query the PublicFolders

This is example of the wrong response I got

    <?xml version="1.0" encoding="utf-8"?>
<s:Envelope xmlns:s="http://schemas.xmlsoap.org/soap/envelope/">
<s:Header>
	<h:ServerVersionInfo MajorVersion="15" MinorVersion="20" MajorBuildNumber="6298" MinorBuildNumber="30" Version="V2018_01_08" xmlns:h="http://schemas.microsoft.com/exchange/services/2006/types" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"/>
</s:Header>
<s:Body>
	<m:GetFolderResponse xmlns:m="http://schemas.microsoft.com/exchange/services/2006/messages" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:t="http://schemas.microsoft.com/exchange/services/2006/types">
		<m:ResponseMessages>
			<m:GetFolderResponseMessage ResponseClass="Success">
				<m:ResponseCode>NoError</m:ResponseCode>
				<m:Folders>
					<t:Folder>
						<t:FolderId Id="<?xml version=" 1.0" encoding="utf-8" ?><s:Envelope xmlns:s="http://schemas.xmlsoap.org/soap/envelope/">
							<s:Header>
								<Action s:mustUnderstand="1" xmlns="http://schemas.microsoft.com/ws/2005/05/addressing/none">*</Action>
							</s:Header>
							<s:Body>
								<s:Fault>
									<faultcode xmlns:a="http://schemas.microsoft.com/exchange/services/2006/types">a:ErrorInternalServerError</faultcode>
									<faultstring xml:lang="en-US">An internal server error occurred. The operation failed.</faultstring>
									<detail>
										<e:ResponseCode xmlns:e="http://schemas.microsoft.com/exchange/services/2006/errors">ErrorInternalServerError</e:ResponseCode>
										<e:Message xmlns:e="http://schemas.microsoft.com/exchange/services/2006/errors">An internal server error occurred. The operation failed.</e:Message>
									</detail>
								</s:Fault>
							</s:Body>
						</s:Envelope>

Look on t:FolderId Id="
As you can see the "InternalServerError" xml message merged with original GetFodlerResponse message and response no more readable!
I pretty sure the problem come somewhere from Microsoft side.