Or, if you wanted to be extra careful, just introduce a new locking flag (LOCK_DONT_LOCK_CAN_DELETE or whatever :-)). Then bug the authors of the most popular editors and the most buggy applications (which block files unneccesarily) to set the flag. If you want to, you could create a compatibility shim to force enable / disable this feature for a given application. (Edit: apparently this flag already exists? FILE_SHARE_DELETE?)
This is tricky, but probably not harder than e.g. modernizing the console subsystem.
I suspect that the breakage would be fairly limited, and I for one would love for this to happen. The amount of stuff which can't be done because of this design decision is huge; proper package management without numerous reboots would be one, and I think the benefit of that and having semantics common with Unix platforms would outweigh the breakage.
The `mklink` tool in Windows is also by no means new; it's been around for many years. It just wasn't very useful since you needed to be an admin to use symbolic links, anyway.