This can be a good thing. The first thing I recommend you do is learn about views. Views are simply stored queries. Views are your friend.
For example instead of having to look for "Where Deleted not null" in your base table, you could create a view called viewActiveWhatever and filter the view so it only produces data where Delete is not null. Remember, views are your friend.
Soft deletes (marked as deleted) vs Hard deletes (Poof it's really gone). This can really mess things up depending on what kinda of data structure you have in place.
- If you mark as deleted and rely on views that show only active data (Remember, views are your friend) it works nicely.
- Some data (especially inner joined data may appear to be missing when it's not)
Not to make this any more difficult but, it sometimes is nice to preserve how something looked prior to it being changed. So, simply placing a modified date on a data row only tells you when that row was changed... it doesn't tell you what was changed.
Now if the data you are refering to is called "Control Data" you might want to consider keeping a historical table. Then before each update to a record in a control table you insert the current data row to the historical table and then make your update. Now you have a permanent record of what was changed and can go back over time and see all the changes.
If you do all your updates in stored procedures, this kind of record keeping is not that difficult.