How did my photos get transferred to my new iPhone even though they weren't in iCloud?
iCloud keeps your photos, and other documents, in the trash and ready for recovery for 30 days after they're deleted.  

Depending on how many photos &amp; files you have in iCloud, it can take hours or days for a sync to complete.  You didn't indicate if you deleted the photos from iCloud.com or from a device.  You also didn't mention if you had other devices signed-in to the same iCloud account.  It's important to note that iCloud doesn't do real-time syncing of files.  It does it on its own schedule.

When you deleted the photos in iCloud, they went into the Trash.  They were deleted but not technically deleted because iCloud allows you to recover items in the Trash for 30 days.

I'm guessing (and I can only guess here, based on the info provided) that the iCloud deletion of the photos was registered after it did the restore of your new device.  If you have other devices signed-in to the same iCloud account, they might not have received the 'delete' message before you connected your new device.  Therefore, the new device got the "sync all photos" message before getting the "delete all photos" message.  

Confusing, I know.

Go to iCloud.com and verify your photos are in the trash.  If not, you can delete them (again).  Also, you can do a permanent delete from the trash on that site.  

Then allow your new device, and all other devices, to sync again.  This could take several hours or a day.  When that's all done, your photos should be deleted from iCloud as well as deleted from all other signed-in devices.