I have seen this a few times and I know that this will become a larger issue as time goes on.
I have been running SCCM for my company for about 7mths now (we have about 1000 PC's) I have noticed that if a PC needs to be rebuilt, when I reinstall the SCCM client everything looks like it is working correctly on the client side but the PC never shows up on the server and cannot be mannaged. The discovery (locally intiated) works as expected but the Actions tab on the client dialog box never populates? I have been able to work around this in the past a time or two by renaming the PC, (But the last two times that i attempted this it did not work, might be a SP1 thing)