Yes, it is possible to search for deleted iMessages. You can use a third-party data recovery app like FonePaw to recover deleted messages on your iPhone.