Cause:
There's corruption in your public folder store, I see this during Exchange 2003 to 2007 Migrations, quite often some folders will replicate fine and other will not, and there is no rhyme or reason as to why. Then you see this error in the event log, essentially a couple of corrupt messages/items are stopping an entire folder from replicating.

Fix:
There's going to be some downtime to your public folders (sorry)

1. On the Exchange 2003 Server, launch the Exchange System Manager > Drill down to the public folder store > Right click > Dismount > Yes.
2. Now you need to run the isinteg tool, it in the exchsrvr directory in the sub folder called "bin" > Start > Run > cmd {Enter} > cd "c:\program files\exchsrvr\bin\" {enter}.

Note: The path to your \bin folder might be different.

3. Take note of your exchange server name in the example below its CTC-EX2, execute the following command,

isinteg -s CTC-EX2 -fix -test alltests

4. Select the offline database that your public folders are in, (in the example below that's 2).

5. Press Y {enter} to confirm.

4. This will perform 11 different tests, each one will tell you,

x number of errors
x number of warnings
x number of fix(es)
x number of rows <---- ignore this figure its not important.

5. Continue to execute the SAME command until one of two things happens,

a. You get 0 errors, 0 warnings, and 0 fix(es) for everything.
OR
b. You get the same result on one or more tests THREE TIMES IN A ROW.

6. When done, go back to the Exchange System Manager and re-mount the store, apply the cup of coffee rule and check replication.

Comments:

Credit to Debasis at Microsoft for his help.