Pixels are being deleted from my selection when I cut and paste it as a new layer?

Would you provide more screenshots for what you do exactly?!
It is about the way you making selection.

However, when I try this now it always deletes pixels around the selection leaving a gap between the new and old layers.

By @YBLee123

Let me guess you have problem with anti-aliasing https://helpx.adobe.com/photoshop/key-concepts/aliasing-anti-aliasing.html. If that is not the case try suggestions above. By the way, judge at 100% view. There are numerous work-arounds like to copy, not to cut content or to use healing brush or to simply enlarge content for single pixel. 

Have you tried resetting the Photoshop Preferences? They can be found in the Photoshop menu on a Mac and the Edit menu on Windows. Within the General tab is the button Reset Preferences On Quit.

You can use the commands in Select>Modify to edit your selection.
The best way for low quality images is to use the Pen Tool to make the perfect selection.