diff --git a/src/PIL/GifImagePlugin.py b/src/PIL/GifImagePlugin.py
--- a/src/PIL/GifImagePlugin.py
+++ b/src/PIL/GifImagePlugin.py
@@ -553,7 +553,9 @@ def _normalize_palette(
 
     if im.mode == "P":
         if not source_palette:
-            source_palette = im.im.getpalette("RGB")[:768]
+            im_palette = im.getpalette(None)
+            assert im_palette is not None
+            source_palette = bytearray(im_palette)
     else:  # L-mode
         if not source_palette:
             source_palette = bytearray(i // 3 for i in range(768))
@@ -629,7 +631,10 @@ def _write_single_frame(
 def _getbbox(
     base_im: Image.Image, im_frame: Image.Image
 ) -> tuple[Image.Image, tuple[int, int, int, int] | None]:
-    if _get_palette_bytes(im_frame) != _get_palette_bytes(base_im):
+    palette_bytes = [
+        bytes(im.palette.palette) if im.palette else b"" for im in (base_im, im_frame)
+    ]
+    if palette_bytes[0] != palette_bytes[1]:
         im_frame = im_frame.convert("RGBA")
         base_im = base_im.convert("RGBA")
     delta = ImageChops.subtract_modulo(im_frame, base_im)
@@ -984,7 +989,13 @@ def _get_palette_bytes(im: Image.Image) -> bytes:
     :param im: Image object
     :returns: Bytes, len<=768 suitable for inclusion in gif header
     """
-    return bytes(im.palette.palette) if im.palette else b""
+    if not im.palette:
+        return b""
+
+    palette = bytes(im.palette.palette)
+    if im.palette.mode == "RGBA":
+        palette = b"".join(palette[i * 4 : i * 4 + 3] for i in range(len(palette) // 3))
+    return palette
 
 
 def _get_background(
diff --git a/src/PIL/Image.py b/src/PIL/Image.py
--- a/src/PIL/Image.py
+++ b/src/PIL/Image.py
@@ -1066,7 +1066,7 @@ def convert_transparency(
                     trns_im = new(self.mode, (1, 1))
                     if self.mode == "P":
                         assert self.palette is not None
-                        trns_im.putpalette(self.palette)
+                        trns_im.putpalette(self.palette, self.palette.mode)
                         if isinstance(t, tuple):
                             err = "Couldn't allocate a palette color for transparency"
                             assert trns_im.palette is not None
@@ -2182,6 +2182,9 @@ def remap_palette(
                 source_palette = self.im.getpalette(palette_mode, palette_mode)
             else:  # L-mode
                 source_palette = bytearray(i // 3 for i in range(768))
+        elif len(source_palette) > 768:
+            bands = 4
+            palette_mode = "RGBA"
 
         palette_bytes = b""
         new_positions = [0] * 256

diff --git a/Tests/test_file_gif.py b/Tests/test_file_gif.py
--- a/Tests/test_file_gif.py
+++ b/Tests/test_file_gif.py
@@ -1429,3 +1429,21 @@ def test_saving_rgba(tmp_path: Path) -> None:
     with Image.open(out) as reloaded:
         reloaded_rgba = reloaded.convert("RGBA")
         assert reloaded_rgba.load()[0, 0][3] == 0
+
+
+def test_optimizing_p_rgba(tmp_path: Path) -> None:
+    out = str(tmp_path / "temp.gif")
+
+    im1 = Image.new("P", (100, 100))
+    d = ImageDraw.Draw(im1)
+    d.ellipse([(40, 40), (60, 60)], fill=1)
+    data = [0, 0, 0, 0, 0, 0, 0, 255] + [0, 0, 0, 0] * 254
+    im1.putpalette(data, "RGBA")
+
+    im2 = Image.new("P", (100, 100))
+    im2.putpalette(data, "RGBA")
+
+    im1.save(out, save_all=True, append_images=[im2])
+
+    with Image.open(out) as reloaded:
+        assert reloaded.n_frames == 2

GIF optimizer acts wrongly with black pixels when `disposal=2`
### What did you do?

- Create a GIF with these two identically sized (250x217) frames: `green.png` and `red.png`
![green](https://github.com/python-pillow/Pillow/assets/2065805/b1cccecf-e003-47d9-adf4-3cd03d8fc1db)
![red](https://github.com/python-pillow/Pillow/assets/2065805/d1dd583d-d60c-4c52-854c-4a30691fd830)

```python
from PIL import Image

green = Image.open("green.png")
red = Image.open("red.png")
green.save("opt.gif", save_all=True, append_images=[red], disposal=2, loop=0, duration=500) 
```


### What did you expect to happen?

Pillow should create this GIF:

![no_opt](https://github.com/python-pillow/Pillow/assets/2065805/0d36e643-e289-4b26-902e-05ad45368dda)

### What actually happened?

Pillow actually creates this GIF, with the second frame "missing" two pixels in height, which get shown as transparent:
![opt](https://github.com/python-pillow/Pillow/assets/2065805/ee761adb-86a2-4398-9991-4ad7cbd6ddfc)
```sh
> identify opt.gif
opt.gif[0] GIF 250x217 250x217+0+0 8-bit sRGB 32c 0.000u 0:00.000
opt.gif[1] GIF 250x215 250x217+0+0 8-bit sRGB 64c 5237B 0.000u 0:00.000
```

What I discovered so far:
- If the black color gets changed to a black-ish color (e.g., rgb(2, 0, 0)), the issue disappears
- If the `disposal` method is not `2`, the issue disappears
- If `optimize=False`, the issue disappears (see the `no_opt.gif` created above in the "expect to happen" section)

This problem seems related, but not identical, to #8003.

### What are your OS, Python and Pillow versions?

* OS: macOS 14.5
* Python: 3.12.3
* Pillow: 10.4.0

```sh
--------------------------------------------------------------------
Pillow 10.4.0
Python 3.12.3 (main, Apr  9 2024, 08:09:14) [Clang 15.0.0 (clang-1500.3.9.4)]
--------------------------------------------------------------------
Python executable is /Users/lucach/Library/Caches/pypoetry/virtualenvs/pytamaro-5GgIxOWM-py3.12/bin/python
Environment Python files loaded from /Users/lucach/Library/Caches/pypoetry/virtualenvs/pytamaro-5GgIxOWM-py3.12
System Python files loaded from /opt/homebrew/opt/python@3.12/Frameworks/Python.framework/Versions/3.12
--------------------------------------------------------------------
Python Pillow modules loaded from /Users/lucach/Library/Caches/pypoetry/virtualenvs/pytamaro-5GgIxOWM-py3.12/lib/python3.12/site-packages/PIL
Binary Pillow modules loaded from /Users/lucach/Library/Caches/pypoetry/virtualenvs/pytamaro-5GgIxOWM-py3.12/lib/python3.12/site-packages/PIL
--------------------------------------------------------------------
--- PIL CORE support ok, compiled for 10.4.0
*** TKINTER support not installed
--- FREETYPE2 support ok, loaded 2.13.2
--- LITTLECMS2 support ok, loaded 2.16
--- WEBP support ok, loaded 1.4.0
--- WEBP Transparency support ok
--- WEBPMUX support ok
--- WEBP Animation support ok
--- JPEG support ok, compiled for libjpeg-turbo 3.0.3
--- OPENJPEG (JPEG2000) support ok, loaded 2.5.2
--- ZLIB (PNG/ZIP) support ok, loaded 1.3.1
--- LIBTIFF support ok, loaded 4.6.0
--- RAQM (Bidirectional Text) support ok, loaded 0.10.1, fribidi 1.0.14, harfbuzz 8.5.0
*** LIBIMAGEQUANT (Quantization method) support not installed
--- XCB (X protocol) support ok
--------------------------------------------------------------------
```

