If the bitcoin client can't see your coins due to the de- and installation, start bitcoint-qt again with the -rescan option. Your coins should then be in there again.
EDIT: Wait, you completely deleted your bitcoin folder? The program folder or the one in the user directory? Because if it's the later, you just shot yourself in the foot real bad.
No I didnt. There was nothing or little in the wallet to begin with. Yes, I deleted the whole Bitcoin folder (programs/Bitcoin) two times. The same unwanted address somehow gets downloaded when I get the Bitcoin program off the web (brand new).
How in the haybale am I supposed to use the wallet (especially to receive money) if the address is changing all the time? Why does the other computer not change its BTC address and it has plenty of transactions on it?