Deleted elements are marked with a bit for delete, but are not deleted immediately. When a file is accidentally cleaned out, eg with fence void, and the file size remains lalarge, eg 6 megabytes, then all that date is still in the file. IF a compress is done, the file size shrinks, and the data is lost. But if a compress is not done, and the file remains big, then all the deleted data is still in the file, each element with its delete bit set. It is possible to go through and reset those bits, recovering all the date. (if the file has not been compressed. HOW do I do it???
Your description is right for V7 format DGN files, but V8 files are stored much differently. Whenever the elements are saved (which happens frequently as you work, unless you turn off autosave), they are stored in compressed sections and deleted elements are removed. In V8, compress reclaims unused space in the file by essentially moving the compressed blocks to the beginning of the file and getting rid of the empty areas.
If you are using Design History you can go back in time to get those elements back, otherwise, after you exit the file, they are gone for good. Hopefully you have a backup file.
Barry