BUG: Series.replace does not preserve dtype of original Series
- [x] closes #33484
- [x] tests added / passed
- [x] passes `black pandas`
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

Reheating #33622 (stale)
Coverting to draft while I debug @arw2019 the underlying problem (or one of them at least) is that ExtensionBlock._can_hold_element and ExtensionBlock.putmask are completely FUBAR.

I suggest you try adding the two following methods to CategoricalBlock (taken from a branch I have trying to get rid of CategoricalBlock.replace and _replace_list)

```
    def _can_hold_element(self, element: Any) -> bool:
        try:
            self.values._validate_setitem_value(element)
            return True
        except (TypeError, ValueError):
            return False

    def putmask(
        self, mask, new, inplace: bool = False, axis: int = 0, transpose: bool = False
    ) -> List["Block"]:
        if self._can_hold_element(new):
            return super().putmask(mask, new, inplace, axis, transpose)

        # TODO: should this be inplace?
        # TODO: use coerce_to_target_dtype?
        cat = self.values.add_categories(new)
        nb = self.make_block(cat)
        assert nb._can_hold_element(new)
        return nb.putmask(mask, new, inplace, axis, transpose)
```

and in coerce_to_target_dtype just after the is_dtype_equal(self.dtype, dtype) check:

```
        if self._can_hold_element(other):
            return self
        elif self.is_categorical:
            # Note: this will be wrong if we ever have a tuple category
            cat = self.values.add_categories(other)
            return self.make_block(cat)
```

This changes the behavior for a handful of tests causing Series/DataFrame.replace to return CategoricalDtype (with added categories) instead of object-dtype, so may not be _quite_ what we want.  But I'm pretty sure its in the right ballpark. > if self._can_hold_element(other):
>             return self
>         elif self.is_categorical:
>             # Note: this will be wrong if we ever have a tuple category
>             cat = self.values.add_categories(other)
>             return self.make_block(cat)

Thanks!!! Pushed this, will see what fails

Update: there are 7 test failures:
```
FAILED pandas/tests/arrays/categorical/test_replace.py::test_replace[to_replace10-value10-expected10-True]
FAILED pandas/tests/frame/indexing/test_categorical.py::TestDataFrameIndexingCategorical::test_assigning_ops
FAILED pandas/tests/frame/methods/test_replace.py::TestDataFrameReplace::test_replace_intervals
FAILED pandas/tests/series/methods/test_replace.py::TestSeriesReplace::test_replace_mixed_types
FAILED pandas/tests/series/methods/test_replace.py::TestSeriesReplace::test_replace_categorical[categorical0-numeric0]
FAILED pandas/tests/series/methods/test_replace.py::TestSeriesReplace::test_replace_categorical[categorical1-numeric1]
FAILED pandas/tests/series/methods/test_replace.py::TestSeriesReplace::test_replace_categorical[categorical2-numeric2]
```
Unfortunately they're undesirable behavioral changes (e.g. replacing a categorical with non-identical categories no longer raises, etc.)

xref #36226, November 2020 dev call 

Mothballing this to clear the queue  cc @jorisvandenbossche the latest commit here is pretty much exactly the edits i was referring to re CategoricalBlock.replace.  Only difference is I would also remove CategoricalBlock.replace and _replace_list.