No, this is not a slam on Lotus Notes.  This one is our fault.  (I did found Paul’s recent blog particularly hilarious, though.)

If you take a look at the following KB article you might get the idea that this fix is included in Exchange 2003 SP1. 
840668 Many Lotus Notes proxy addresses appear in the properties of a user account in a domain where Exchange Server 2003 is installed

The version of ntspxgen.dll in the article is 6.5.6980.87 and SP1 should bring everyone up to 6.5.7226.0 (at least).  And it was supposed to be included in SP1, but it didn't make it for some reason.  (We did get the SMTP fix and others for the same issue into SP1.)  So, why might you need the fix?  Well, in certain circumstances the RUS can go a little crazy and start stamping objects over and over again adding NOTES addresses again and again.  Soon you may get to a point where you have "packed pages" (Event ID 1171 with error -1026) and the replication between you 5.5 environment and your Active Directory may stop.  Once you get to this point you have to do some work to get rid of the extra proxy addresses.  See 318774 Removing duplicate and unwanted proxy addresses in Exchange more information on how to resolve it.

If you don't have SP1 already installed and need to install the fix, you can get the hot fix from some of the support options at http://support.microsoft.com/oas/default.aspx?&gprid=1773.  If you already have SP1 installed you may request the POST SP1 fix, otherwise you will get an error during install with the PRE SP1 fix mentioned above.