No, they're not still on the phone, although they may have left bits of themselves behind on the SD card.
There are multiple types of memory on an Android device. There's RAM, where applications execute (just like on a PC). And there's storage, which is like the disk drive on a PC. Deleting an app from program storage won't impact free RAM memory, which is probably what you're looking at when you say your memory space didn't change.
Another thought: If the program was resident in memory, either in the foreground or background, deleting the app from storage memory might not affect the currently "executing" copy of that app. A reboot (turn phone off and on) will clear that out. So will just waiting, because eventually Android will reuse that memory space for something else.
Third thought: Android abhors a memory vacuum. If you remove an app from (RAM) memory, Android will probably load something else in there. Unlike Windows or BB, having lots of things in memory isn't bad. Android will reuse memory as needed.