diff --git a/doc/release_notes/v2.0.0.rst b/doc/release_notes/v2.0.0.rst
index ae211abd9..20c2325a5 100644
--- a/doc/release_notes/v2.0.0.rst
+++ b/doc/release_notes/v2.0.0.rst
@@ -36,5 +36,6 @@ Fixes
   (0028,3006) *LUT Data* with a VR of **OW** (:issue:`1073`)
 * Fixed access to private creator tag in raw datasets (:issue:`1078`)
 * Fixed description of newly added known private tag (:issue:`1082`)
+* Fixed update of private blocks after deleting private creator (:issue:`1097`)
 * Fixed bug in updating `pydicom.config.use_DS_Decimal` flag
   in :func:`~pydicom.config.DS_decimal`
diff --git a/pydicom/dataset.py b/pydicom/dataset.py
index ec8f68196..da486df83 100644
--- a/pydicom/dataset.py
+++ b/pydicom/dataset.py
@@ -581,14 +581,22 @@ class Dataset(dict):
         if isinstance(key, slice):
             for tag in self._slice_dataset(key.start, key.stop, key.step):
                 del self._dict[tag]
+                # invalidate private blocks in case a private creator is
+                # deleted - will be re-created on next access
+                if self._private_blocks and BaseTag(tag).is_private_creator:
+                    self._private_blocks = {}
         else:
             # Assume is a standard tag (for speed in common case)
             try:
                 del self._dict[key]
+                if self._private_blocks and BaseTag(key).is_private_creator:
+                    self._private_blocks = {}
             # If not a standard tag, than convert to Tag and try again
             except KeyError:
                 tag = Tag(key)
                 del self._dict[tag]
+                if self._private_blocks and tag.is_private_creator:
+                    self._private_blocks = {}
 
     def __dir__(self):
         """Give a list of attributes available in the :class:`Dataset`.
@@ -905,7 +913,7 @@ class Dataset(dict):
             If the private creator tag is not found in the given group and
             the `create` parameter is ``False``.
         """
-        def new_block():
+        def new_block(element):
             block = PrivateBlock(key, self, element)
             self._private_blocks[key] = block
             return block
@@ -921,19 +929,23 @@ class Dataset(dict):
             raise ValueError(
                 'Tag must be private if private creator is given')
 
-        for element in range(0x10, 0x100):
-            private_creator_tag = Tag(group, element)
-            if private_creator_tag not in self._dict:
-                if create:
-                    self.add_new(private_creator_tag, 'LO', private_creator)
-                    return new_block()
-                else:
-                    break
-            if self[private_creator_tag].value == private_creator:
-                return new_block()
+        # find block with matching private creator
+        data_el = next((el for el in self[(group, 0x10):(group, 0x100)]
+                        if el.value == private_creator), None)
+        if data_el is not None:
+            return new_block(data_el.tag.element)
+
+        if not create:
+            # not found and shall not be created - raise
+            raise KeyError(
+                "Private creator '{}' not found".format(private_creator))
 
-        raise KeyError(
-            "Private creator '{}' not found".format(private_creator))
+        # private creator not existing - find first unused private block
+        # and add the private creator
+        first_free_el = next(el for el in range(0x10, 0x100)
+                             if Tag(group, el) not in self._dict)
+        self.add_new(Tag(group, first_free_el), 'LO', private_creator)
+        return new_block(first_free_el)
 
     def private_creators(self, group):
         """Return a list of private creator names in the given group.
@@ -967,13 +979,7 @@ class Dataset(dict):
         if group % 2 == 0:
             raise ValueError('Group must be an odd number')
 
-        private_creators = []
-        for element in range(0x10, 0x100):
-            private_creator_tag = Tag(group, element)
-            if private_creator_tag not in self._dict:
-                break
-            private_creators.append(self[private_creator_tag].value)
-        return private_creators
+        return [x.value for x in self[(group, 0x10):(group, 0x100)]]
 
     def get_private_item(self, group, element_offset, private_creator):
         """Return the data element for the given private tag `group`.

Unexpected behavior on re-adding a private tag to a dataset after remove_private_tags
I've encountered this issue while trying to write a solution to #1087.
I'm trying to add a past private tag to a dataset that had all his private tags removed with remove_private_tags. It leads to a single element update - just the private tag data. No private creator element is added. Also, the private tag is updated on the second free block rather than the first - that's supposed to be free after remove_private_tags.
It seems the dataset preserves some information on past private creators blocks even after remove_private_tags. 

I expect that a private creator element would be (re-)created if I'm trying to add a private tag, and that it would created on the first available place in the private group.

Reproducing code:
```
from pydicom import Dataset

ds = Dataset()
block = ds.private_block(0x000b, 'dog^1', create=True)
block.add_new(0x01, "SH", "Border Collie")
block = ds.private_block(0x000b, 'dog^2', create=True)
block.add_new(0x01, "SH", "Poodle")

ds.remove_private_tags()
block = ds.private_block(0x000b, 'dog^2', create=True)
block.add_new(0x01, "SH", "Poodle")
print(ds)

```
Output:
```
(000b, 1101) Private tag data                    SH: 'Poodle'`
```

Aa far as I understand, output should be:
```
(000b, 0010) Private Creator                     LO: 'dog^2'
(000b, 1001) Private tag data                    SH: 'Poodle'
```

My environment (Running with docker from PyCharm):
Linux-4.15.0-74-generic-x86_64-with-debian-buster-sid
Python 3.6.9 |Anaconda, Inc.| (default, Jul 30 2019, 19:07:31)
[GCC 7.3.0]
pydicom 2.0.0.dev
```
diff --git a/pydicom/tests/test_dataset.py b/pydicom/tests/test_dataset.py
index 78e2083d1..d3efc2079 100644
--- a/pydicom/tests/test_dataset.py
+++ b/pydicom/tests/test_dataset.py
@@ -917,9 +917,10 @@ class TestDataset(object):
         ds.add_new(0x00080005, 'CS', 'ISO_IR 100')
         ds.add_new(0x00090010, 'LO', 'Creator 1.0')
         ds.add_new(0x00091001, 'SH', 'Version1')
-        ds.add_new(0x00090011, 'LO', 'Creator 2.0')
-        ds.add_new(0x00091101, 'SH', 'Version2')
-        ds.add_new(0x00091102, 'US', 2)
+        # make sure it works with non-contiguous blocks
+        ds.add_new(0x00090020, 'LO', 'Creator 2.0')
+        ds.add_new(0x00092001, 'SH', 'Version2')
+        ds.add_new(0x00092002, 'US', 2)
 
         # Dataset.private_block
         with pytest.raises(ValueError, match='Tag must be private'):
@@ -1019,6 +1020,68 @@ class TestDataset(object):
         assert ['Creator 1.0', 'Creator 2.0'] == ds.private_creators(0x0009)
         assert not ds.private_creators(0x0011)
 
+    def test_non_contiguous_private_creators(self):
+        ds = Dataset()
+        ds.add_new(0x00080005, 'CS', 'ISO_IR 100')
+        ds.add_new(0x00090010, 'LO', 'Creator 1.0')
+        ds.add_new(0x00090020, 'LO', 'Creator 2.0')
+        ds.add_new(0x000900ff, 'LO', 'Creator 3.0')
+
+        assert (['Creator 1.0', 'Creator 2.0', 'Creator 3.0'] ==
+                ds.private_creators(0x0009))
+
+    def test_create_private_tag_after_removing_all(self):
+        # regression test for #1097 - make sure private blocks are updated
+        # after removing all private tags
+        ds = Dataset()
+        block = ds.private_block(0x000b, 'dog^1', create=True)
+        block.add_new(0x01, "SH", "Border Collie")
+        block = ds.private_block(0x000b, 'dog^2', create=True)
+        block.add_new(0x01, "SH", "Poodle")
+
+        ds.remove_private_tags()
+        block = ds.private_block(0x000b, 'dog^2', create=True)
+        block.add_new(0x01, "SH", "Poodle")
+        assert len(ds) == 2
+        assert (0x000b0010) in ds
+        assert ds[0x000b0010].value == 'dog^2'
+
+    def test_create_private_tag_after_removing_private_creator(self):
+        ds = Dataset()
+        block = ds.private_block(0x000b, 'dog^1', create=True)
+        block.add_new(0x01, "SH", "Border Collie")
+
+        del ds[0x000b0010]
+        block = ds.private_block(0x000b, 'dog^1', create=True)
+        block.add_new(0x02, "SH", "Poodle")
+        assert len(ds) == 3
+        assert ds[0x000b0010].value == 'dog^1'
+
+        del ds[Tag(0x000b, 0x0010)]
+        block = ds.private_block(0x000b, 'dog^1', create=True)
+        block.add_new(0x01, "SH", "Pug")
+        assert len(ds) == 3
+        assert ds[0x000b0010].value == 'dog^1'
+
+        del ds['0x000b0010']
+        block = ds.private_block(0x000b, 'dog^1', create=True)
+        block.add_new(0x01, "SH", "Pug")
+        assert len(ds) == 3
+        assert ds[0x000b0010].value == 'dog^1'
+
+    def test_create_private_tag_after_removing_slice(self):
+        ds = Dataset()
+        block = ds.private_block(0x000b, 'dog^1', create=True)
+        block.add_new(0x01, "SH", "Border Collie")
+        block = ds.private_block(0x000b, 'dog^2', create=True)
+        block.add_new(0x01, "SH", "Poodle")
+
+        del ds[0x000b0010:0x000b1110]
+        block = ds.private_block(0x000b, 'dog^2', create=True)
+        block.add_new(0x01, "SH", "Poodle")
+        assert len(ds) == 2
+        assert ds[0x000b0010].value == 'dog^2'
+
     def test_is_original_encoding(self):
         """Test Dataset.write_like_original"""
         ds = Dataset()

pip install -e .[dev]
parse_log_pytest
requirements.txt
numpy>=1.16.0 pytest pytest-cov
apt-get update apt-get install -y gcc
3.9
requirements/base.txt
pytest --no-header -rA --tb=line --color=no -p no:cacheprovider -W ignore::DeprecationWarning
coverage==7.8.0
exceptiongroup==1.2.2
iniconfig==2.1.0
numpy==2.0.2
packaging==24.2
pluggy==1.5.0
-e git+https://github.com/pydicom/pydicom.git@64e0ac1daca1ef62066454dbe596b2d8de9058a1#egg=pydicom
pytest==8.3.5
pytest-cov==6.0.0
tomli==2.2.1

name: pydicom
channels:
  - defaults
  - https://repo.anaconda.com/pkgs/main
  - https://repo.anaconda.com/pkgs/r
  - conda-forge
dependencies:
  - _libgcc_mutex=0.1=main
  - _openmp_mutex=5.1=1_gnu
  - ca-certificates=2025.2.25=h06a4308_0
  - ld_impl_linux-64=2.40=h12ee557_0
  - libffi=3.4.4=h6a678d5_1
  - libgcc-ng=11.2.0=h1234567_1
  - libgomp=11.2.0=h1234567_1
  - libstdcxx-ng=11.2.0=h1234567_1
  - ncurses=6.4=h6a678d5_0
  - openssl=3.0.16=h5eee18b_0
  - pip=25.0=py39h06a4308_0
  - python=3.9.21=he870216_1
  - readline=8.2=h5eee18b_0
  - setuptools=75.8.0=py39h06a4308_0
  - sqlite=3.45.3=h5eee18b_0
  - tk=8.6.14=h39e8969_0
  - tzdata=2025a=h04d1e81_0
  - wheel=0.45.1=py39h06a4308_0
  - xz=5.6.4=h5eee18b_1
  - zlib=1.2.13=h5eee18b_1
  - pip:
      - coverage==7.8.0
      - exceptiongroup==1.2.2
      - iniconfig==2.1.0
      - numpy==2.0.2
      - packaging==24.2
      - pluggy==1.5.0
      - pytest==8.3.5
      - pytest-cov==6.0.0
      - tomli==2.2.1
prefix: /opt/conda/envs/pydicom

pydicom/tests/test_dataset.py::TestDataset::test_private_block pydicom/tests/test_dataset.py::TestDataset::test_non_contiguous_private_creators pydicom/tests/test_dataset.py::TestDataset::test_create_private_tag_after_removing_all pydicom/tests/test_dataset.py::TestDataset::test_create_private_tag_after_removing_private_creator pydicom/tests/test_dataset.py::TestDataset::test_create_private_tag_after_removing_slice
pydicom/tests/test_dataset.py::TestDataset::test_set_existing_data_element_by_name pydicom/tests/test_dataset.py::TestDataset::test_membership pydicom/tests/test_dataset.py::TestDataset::test_contains pydicom/tests/test_dataset.py::TestDataset::test_clear pydicom/tests/test_dataset.py::TestDataset::test_pop pydicom/tests/test_dataset.py::TestDataset::test_pop_using_tuple pydicom/tests/test_dataset.py::TestDataset::test_pop_using_keyword pydicom/tests/test_dataset.py::TestDataset::test_popitem pydicom/tests/test_dataset.py::TestDataset::test_setdefault pydicom/tests/test_dataset.py::TestDataset::test_setdefault_tuple pydicom/tests/test_dataset.py::TestDataset::test_setdefault_use_value pydicom/tests/test_dataset.py::TestDataset::test_setdefault_keyword pydicom/tests/test_dataset.py::TestDataset::test_get_exists1 pydicom/tests/test_dataset.py::TestDataset::test_get_exists2 pydicom/tests/test_dataset.py::TestDataset::test_get_exists3 pydicom/tests/test_dataset.py::TestDataset::test_get_exists4 pydicom/tests/test_dataset.py::TestDataset::test_get_default1 pydicom/tests/test_dataset.py::TestDataset::test_get_default2 pydicom/tests/test_dataset.py::TestDataset::test_get_default3 pydicom/tests/test_dataset.py::TestDataset::test_get_default4 pydicom/tests/test_dataset.py::TestDataset::test_get_raises pydicom/tests/test_dataset.py::TestDataset::test_named_member_updated pydicom/tests/test_dataset.py::TestDataset::test_update pydicom/tests/test_dataset.py::TestDataset::test_dir pydicom/tests/test_dataset.py::TestDataset::test_dir_filter pydicom/tests/test_dataset.py::TestDataset::test_delete_dicom_attr pydicom/tests/test_dataset.py::TestDataset::test_delete_dicom_command_group_length pydicom/tests/test_dataset.py::TestDataset::test_delete_other_attr pydicom/tests/test_dataset.py::TestDataset::test_delete_item_long pydicom/tests/test_dataset.py::TestDataset::test_delete_item_tuple pydicom/tests/test_dataset.py::TestDataset::test_delete_non_existing_item pydicom/tests/test_dataset.py::TestDatasetElements::test_sequence_assignment pydicom/tests/test_dataset.py::TestDatasetElements::test_ensure_file_meta pydicom/tests/test_dataset.py::TestDatasetElements::test_fix_meta_info pydicom/tests/test_dataset.py::TestFileDataset::test_pickle pydicom/tests/test_dataset.py::TestFileDataset::test_pickle_modified pydicom/tests/test_dataset.py::TestFileDataset::test_equality_file_meta pydicom/tests/test_dataset.py::TestDatasetOverlayArray::test_no_possible pydicom/tests/test_dataset.py::TestDatasetOverlayArray::test_possible_not_available pydicom/tests/test_dataset.py::TestDatasetOverlayArray::test_possible_available pydicom/tests/test_dataset.py::TestDatasetOverlayArray::test_handler_raises
pydicom/tests/test_dataset.py::TestDataset::test_attribute_error_in_property pydicom/tests/test_dataset.py::TestDataset::test_for_stray_raw_data_element pydicom/tests/test_dataset.py::TestDataset::test_attribute_error_in_property_correct_debug pydicom/tests/test_dataset.py::TestDataset::test_tag_exception_print pydicom/tests/test_dataset.py::TestDataset::test_tag_exception_walk pydicom/tests/test_dataset.py::TestDataset::test_set_new_data_element_by_name pydicom/tests/test_dataset.py::TestDataset::test_set_non_dicom pydicom/tests/test_dataset.py::TestDataset::test_get_from_raw pydicom/tests/test_dataset.py::TestDataset::test__setitem__ pydicom/tests/test_dataset.py::TestDataset::test_matching_tags pydicom/tests/test_dataset.py::TestDataset::test_dir_subclass pydicom/tests/test_dataset.py::TestDataset::test_delete_dicom_attr_we_dont_have pydicom/tests/test_dataset.py::TestDataset::test_equality_no_sequence pydicom/tests/test_dataset.py::TestDataset::test_equality_private pydicom/tests/test_dataset.py::TestDataset::test_equality_sequence pydicom/tests/test_dataset.py::TestDataset::test_equality_not_dataset pydicom/tests/test_dataset.py::TestDataset::test_equality_unknown pydicom/tests/test_dataset.py::TestDataset::test_equality_inheritance pydicom/tests/test_dataset.py::TestDataset::test_equality_elements pydicom/tests/test_dataset.py::TestDataset::test_inequality pydicom/tests/test_dataset.py::TestDataset::test_hash pydicom/tests/test_dataset.py::TestDataset::test_property pydicom/tests/test_dataset.py::TestDataset::test_add_repeater_elem_by_keyword pydicom/tests/test_dataset.py::TestDataset::test_setitem_slice_raises pydicom/tests/test_dataset.py::TestDataset::test_getitem_slice_raises pydicom/tests/test_dataset.py::TestDataset::test_empty_slice pydicom/tests/test_dataset.py::TestDataset::test_getitem_slice pydicom/tests/test_dataset.py::TestDataset::test_getitem_slice_ffff pydicom/tests/test_dataset.py::TestDataset::test_delitem_slice pydicom/tests/test_dataset.py::TestDataset::test_group_dataset pydicom/tests/test_dataset.py::TestDataset::test_get_item pydicom/tests/test_dataset.py::TestDataset::test_get_item_slice pydicom/tests/test_dataset.py::TestDataset::test_get_private_item pydicom/tests/test_dataset.py::TestDataset::test_private_creator_from_raw_ds pydicom/tests/test_dataset.py::TestDataset::test_add_known_private_tag pydicom/tests/test_dataset.py::TestDataset::test_add_new_private_tag pydicom/tests/test_dataset.py::TestDataset::test_delete_private_tag pydicom/tests/test_dataset.py::TestDataset::test_private_creators pydicom/tests/test_dataset.py::TestDataset::test_is_original_encoding pydicom/tests/test_dataset.py::TestDataset::test_remove_private_tags pydicom/tests/test_dataset.py::TestDataset::test_data_element pydicom/tests/test_dataset.py::TestDataset::test_iterall pydicom/tests/test_dataset.py::TestDataset::test_save_as pydicom/tests/test_dataset.py::TestDataset::test_save_as_compressed_no_encaps pydicom/tests/test_dataset.py::TestDataset::test_save_as_compressed_encaps pydicom/tests/test_dataset.py::TestDataset::test_save_as_no_pixel_data pydicom/tests/test_dataset.py::TestDataset::test_save_as_no_file_meta pydicom/tests/test_dataset.py::TestDataset::test_save_as_private_transfer_syntax pydicom/tests/test_dataset.py::TestDataset::test_save_as_set_little_implicit_with_tsyntax pydicom/tests/test_dataset.py::TestDataset::test_save_as_undefined pydicom/tests/test_dataset.py::TestDataset::test_save_as_undefined_private pydicom/tests/test_dataset.py::TestDataset::test_save_as_undefined_no_tsyntax pydicom/tests/test_dataset.py::TestDataset::test_with pydicom/tests/test_dataset.py::TestDataset::test_exit_exception pydicom/tests/test_dataset.py::TestDataset::test_pixel_array_already_have pydicom/tests/test_dataset.py::TestDataset::test_pixel_array_id_changed pydicom/tests/test_dataset.py::TestDataset::test_pixel_array_unknown_syntax pydicom/tests/test_dataset.py::TestDataset::test_formatted_lines pydicom/tests/test_dataset.py::TestDataset::test_formatted_lines_known_uid pydicom/tests/test_dataset.py::TestDataset::test_set_convert_private_elem_from_raw pydicom/tests/test_dataset.py::TestDataset::test_top pydicom/tests/test_dataset.py::TestDataset::test_trait_names pydicom/tests/test_dataset.py::TestDataset::test_walk pydicom/tests/test_dataset.py::TestDataset::test_update_with_dataset pydicom/tests/test_dataset.py::TestDatasetElements::test_validate_and_correct_file_meta pydicom/tests/test_dataset.py::TestFileDataset::test_creation_with_container pydicom/tests/test_dataset.py::TestFileDataset::test_works_as_expected_within_numpy_array pydicom/tests/test_dataset.py::TestFileDataset::test_dataset_overrides_all_dict_attributes
pydicom/dataset.py doc/release_notes/v2.0.0.rst
pydicom/dataset.py doc/release_notes/v2.0.0.rst