Where's royal when you need him?

I have a problem with a shared mailbox. Basically there are around 20 people have access to this mailbox and when anyone of them try to run a search on the mailbox they get the error:
there are too many find public folders dialogs open. you must close them to use the advanced find. Do you want to close them now?
You then can choose yes or no.
Then it states "outlook cannot perform your search. Outlook cannot display this view. the folder already exists"
Does anyone have any ideas?
Ive ran outlook /cleanfinders (from MS article 240697). Sometimes it works but then returns soon after or it doesnt work and you get the same error.
The mailbox has been used for quite a while and has just started happening.
Does anyone have any idea's? Cheers