Are iMessages saved to iCloud even if iCloud is turned off on my phone?
iMessages are stored in the iMessage service on your Apple ID. They are completely separate from iCloud. Turning on iMessage will store your messages on Apple's servers, regardless of iCloud setting.

Deleting an iMessage does not delete it from all your currently-authenticated devices but the message won't show on future authenticated devices.