Windows Forms applications can also use the ProgressBar class.
If this is a long-running task, are you performing work in a background thread? Consider the BackgroundWorker class if you haven't already; it works nicely with progress bars and labels.
I don't want to use a true MessageBox as I don't want the user to have to click OK each time
I agree 110%; I'd never use a message box in something that will be seen by actual users. There are always better ways to handle the communication.