woocommerce_items_in_cart & woocommerce_cart_hash cookies rejected expired

Hi,

We recently having issue about cookie rejection and expired (when we try to add products to cart OR remove items/products from cart) as I see following in console, please see screenshot https://paste.pics/AAXT2

Cookie “woocommerce_items_in_cart” has been rejected because it is already expired.
Cookie “woocommerce_cart_hash” has been rejected because it is already expired.

Issue 1: When we have multiple products in Cart and try to remove those via X icon, the last product doesn’t get removed sometime, it gets removed if we try again in 2nd or 3rd attempt.
Sometime on removing product, it adds products again to cart.

Issue 2: Sometime when a customer add a product to cart, it adds multiple other products randomly in cart also (that also for repeating customers/users) who may have added those products before.

Steps to Re-Produce issues:
It seems to work fine the first time you visit the page, then it is caching the IP and when you return to the cart it’s adding in heaps of random items to the cart.
You need to visit website on mobile/desktop 2 to 3 times.
You can add products on cart 1st time, then come again to website to add more products or removing products, you will see issue on LIVE website at-least for removing products from cart issue.

Please note that Cart, Checkout pages etc are excluded from Cache, when checked remove from cart etc requests bypassing issue.

Current Hosting is Kinsta LIVE URL https://www.schmarr.com.au/ :
We have tried it without Kinsta cache, WP Rocket or any CDN as well but issue still come.
Kinsta Staging without any cache plugin: https://staging-schmarr.temp513.kinsta.cloud/

We recently changed hosting from Godaddy to Kinsta 10 days ago.
We noticed this issue recently on Kinsta only (but to mention that website was LIVE for customers on Godaddy only for a 1 week before we migrated to Kinsta).

But during debugging today, I noticed issue on old Godaddy staging https://22z.ce1.myftpupload.com also about removing product from cart as it removed last product on 2nd attempt.

So can you please explain what possible reason/solution can be for this issue?