In WinForms you could set a progress bar to loop endlessly to indicate that you don't know how long it will take. How would I do that in WPF?
I personally like the approach Visual Studio 2010 takes. They use an animation of a small, looping series of dots (with varying intensity). They just animate the dots circling in the center of the window in question.
In WPF, this is trivial - just animate a rotation of a small drawing of a circle of dots with the opacity set correctly up front.
I find it very intuitive, small, and unintrusive.
Is a progress bar the right widget for this? You are unable to indicate a % complete, since you "don't know how long it will take". Maybe an animation of some sort (like the Windows files-disappearing-into-thin-air-while-deleting effect) to show that activity is still going on would be better. But a "progress" bar that simply resets to zero because there is still more work to do just looks dumb to me.