Permanently deleted synced Lightroom photos from phone still appearing in Photoshop

I assume that when you click on Your Work>Lightroom photos in PS that you see the thumbnails of the images that you deleted? They're not actually "in" Photoshop, that's simply a link to your cloud account....so if the images are being shown there it would tend to indicate that they haven't been deleted.

Have you checked your cloud account using the Lightroom Web portal? Login at lightroom.adobe.com and you'll see what images are still in your cloud account, and if you want to delete them all you can click on your avatar top right, select Account Info and you'll see the option to "Delete Lightroom Library". That's the nuclear option, click that button and all the images that you've synced to the Adobe cloud will be removed....so only use it if you are certain that's what you are wanting to do. If you are only trying to delete the images that have been synced from your phone, that should be fairly simple without taking the drastic step of deleting the entire cloud library.