I believe I found the solution to this problem.
The problem is with the way Microsoft deals with Focused inbox.
Goto Settings > Mail > Layout > Focused Inbox select "Don't sort my messages".

I have 3 emails with the new Outlook application. Two of the emails had the "Don't sort my messages" while one email had the "Sort messages into Focused and Other". The one email that had the sorting option enabled faced the problem, while the other two did not. I checked this by going to the web version of GMAIL of all three emails and doing a mark as read back and forth.
The problem seems to have been fixed for me for the past 3 days. However, I am going to keep an eye on the situation
Regards