Just to let you know I've experienced the spatial join bug found in SP4.
I was joining 740000+ points to 13 polygons
Just under 19000 records had attribute data come across. The rest were all null.
I've run the exact same data on another machine with ArcGIS 10 SP3 and it worked fine.
I see there was a bug listed ( NIM079126 ) but for some reason it's been declined. Not sure why this is, but you should know this is happening to others.
One thing I noticed was the last record to have an entry before the attributes failed to populate was a point that was outside all polygons I was trying to join to. I'd suggest creating a point dataset with one point outisde the main body of a join polygon to test this. Maybe then we can see some work towards a solution.