If I had to take a wild guess, it seems the flag that indicates a message was sent is not getting marked.. ( believe someone stated this also before ) .. Happens randomly, messages can come in several minutes / hours a part.. And can happen after a reboot..
If someone is "Sending Duplicate" that may be different problem.. Since it seems like most here are only receiving the duplicates..
I also agree, just make a quick call or email to VZW so they understand it's a widespread issue.
Hope the Gingerbread is getting tooled the right way.. (also hoping for Swype V3, cant seem to load the Beta)