Unfortunately, it appears that your battery health is gone for good. As of the iPhone XS, Apple started pairing batteries with logic boards so that if you don't have Apple or an authorized repair center replace the battery you lose your battery health and get the non-genuine warning even if you use a genuine Apple battery.
So far the only way around that is to buy a battery without the Battery Management System (BMS) on it and transfer the one from your original battery onto the replacement cell. The battery statistics can then be reset and you'd be all set.
Of course, it appears your original battery is long gone, so that won't help you now; only Apple can fix that at this point, although you could use their self repair program as long as you buy the battery from them and rent their tools to do the job. I assume there's no chance of getting your original battery back from the shop, is there?
None of which helps you with your shutdown problem though. Alisha, (@flannelist) have you run into anything like this?
Sounds like it may be time for a second opinion. I'm not sure if Apple will help you or not after having the battery replaced by a non-authorized shop.