Ren, my first advice is to call an electrician, and let him figure it out. You don’t want to be guessing with electricity. gapcity’s remark about you beiong lucky there wasn’t 240 volts in there is on the money. A professor (EE, no less) I knew from college set his printer on fire once. Each outlet pair in the room had the top outlet on one leg, and the other outlet on the other leg. He didn’t know this, and put 240 through his printer when he wired it up differently.
If you ignore my advice above, then at least find out exactly what you have going on. It sounds like you may have a circuit (black/white/ground) going directly to the outlet, and another circuit going through the switch, and on to the outlet, which is not code. When you pull the fuse or switch off breaker to the outlet, have you checked all the wires at the switch, to see if they have power? If so, you have two different circuits. If not, you may still have two circuits both wired into the same fuse.
Also, when you check for power, do you know what voltage you’re getting? If you just have a neon tester, it would still glow at 240. I don’t think it would necessarily burn out.
With the fuse on, but the wires at the outlet disconnected and not touching one another or anything else, the switch off, and the white wires at the switch disconnected, is there power at the switch between a black and white pair? If so, this is the second source of power. (OK, you’ve already done this, and got no power, so skip to the next paragraph.) The other black/white pair of wires probably go to the outlet. With the power off again use a continuity tester to verify that white at the switch is connected to white at the outlet, and the same for black. If more than one pair of black and white have power between them, give up and call an electrician. It’s too messed up.
If none of the pairs have power, some of the wires may just be floating. In testing the wires at the switch, it would also be good to have a known good ground. When you’re testing for power at the switch, if one wire (or two) is at 120 volts, and the others are not connected to anything, you’d never register power. Likewise, when you think you have the wires which go from the outlet to the switch figured out, it would be good to check for voltage or continuity between them and ground.
If you can determine that one black/white pair at the switch goes to the outlet, you can wire up your switch to code*. Continuing with the fuse off, snip off the exposed leads of the black/white pair at the switch which doesn’t go to the outlet, and wrap each separately with electrical tape. You won’t need them. (Actually, you should do the snipping at the end, if everything is working OK.) Connect the black and white wires that go to the outlet to the switch.
Back at the outlet, the black and white coming in with power can be connected up to the unswitched outlet. The White side needs to be connected to the white side of the other outlet, if the tab on the outlet is broken off. You need to connect the black wire to one of the wires which go towards the switch. The other wire from the switch goes to the black screw on the switched outlet.
Remember to observe the correct polarity. Also, make sure that black to ground on the incoming power forms a circuit, and not white to ground. If this is switched, your black and white wires are reversed.
With the switch off, put the fuse back in. The unswitched outlet should work, and the other should be off. Turning on the switch should turn on the switched outlet. I’d cross my fingers here, which is why I’m going to repeat that bringing in an electriciian is a better idea than doing it yourself, even if you’re talking with an electrician on the SDMB (referring to gapcity. I’m not an electrician.).
(*) gapcity seems to contradict this. gapcity, I thought that a black/white pair could be used to run from a light or outlet to the switch controlling it, and back.