Not entirely sure of the context in which you are working (desktop?). I am assuming you don't just mean like a status bar with message, as these often do not get seen.
Lots of applications have clear but not very distracting notifications for spell checking, eg Word, Thunderbird, Chrome, etc. The notification is usually a wiggly coloured line under the error which you can choose to correct manually or get choices/help via a popup menu.
Many IDEs (eg Visual Studio, Eclipse, Qt Creator) have a vertical bar to one side which can indicate errors and their severity against relevant lines. This space is also useful for other information, not just mistakes.
Maybe this isn't relevant to your workflow - you don't tell us about the workflow that you don't want interrupted :)
Personally I find both these systems work just at the right level. I am aware that there is a problem but I can continue without losing train of thought. I can come back to it later. I can see multiple problems all at once when I do come back and I can choose which ones to resolve depending on severity.
It's a tough problem. Any notification in order to make itself known needs to interrupt the user - even if very slightly. The only non-interrupting notification is no notification. I even think sliding or fading popups are too much because they take too long to appear and disappear. Ones that suddenly appear are too distracting, and also once they are gone away, the notification can be forgotten.
I think a permanent but very subtle notification, shown as near to the problem as possible is good. The ability to see a notification in place allows the user to interact with it and find out more information about the problem right there in context.
You could opt to only notify in a stronger way if the user attempts to 'move on' without rectifying problems.
[Edit]
I was just using MS Expression Blend4 after answering this question, and realised they used quite a nice notification system as you work. It did not come to mind earlier because it was not so distracting as to be annoying, remarkable or memorable. [Great ux doesn't get noticed!]. The benefits of this system are:
Tooltips appear pointing out a particular issue.
They are not in contrasting colours to the area I'm working in so they don't distract too much visually.
They point exactly to the particular control that is the cause or where I can correct the problem.
They do not take focus.
They do not hide what you are doing right at time.
They do not stop you typing or carrying on.
They do not go away as you change focus to other parts of the dialog.
You can click on them to dismiss/ignore them
They clearly state the problem and they automatically go away as you correct the problem or do something else that makes the problem go away.
I do not get a stronger error notification until I proceed to the next stage without rectifying the problem.
