For some reason, I cannot convince the app store that an application (Xcode, in this case) is not installed.
I have deleted /Developer (which only contained an old, busted Xcode 3.2.3) and tried to rebuild the LaunchServices DB (using lsregister -kill -r -domain local -domain system -domain user) but to no avail; The app store stubbornly claims that Xcode is already installed.
First, you can try to remove all remaining traces of the old program. Search your whole hard drive (including all partitions and accounts), and attached external drives for related files and remove them.
If you can't get the App Store to believe that you don't have the app anymore, hold down option and click on the Install button. That will let you download it, and the installer will probably work.
This probably indicates that you have a cracked application on your computer. Within the package of each application there is a folder called /Contents/_MASReceipt. This is the Mac App Store Receipt file. A common way for people to crack Mac App store applications is to replace the receipt folder with the receipt of another program that you have legitimately purchased or installed with your Apple ID. Since the receipt for XCode exists within some other application that is not Xcode, you will always see the update until you either install the latest version of Xcode or remove the application (that is not Xcode) that includes the Xcode receipt.