Deleted some apk files - but the apps are still there after reboot This seems really weird to me.

I followed the instructions given here 

http://forum.xda-developers.com/showthread.php?t=835861

and deleted the apk files of some stock applications like Layar. I also removed the odex files if I could find them. 

Strangely, even after wiping the cache and a reboot, I can still run the apps from my launcher. 

Samsung Galaxy S with CWM 3.2
Some vendors set up their phones to reinstall system applications at boot in case they go missing.  Try finding a directory that contains a copy of the APK that's used to reinstall it, and delete it from there.

A simple alternative solution is to freeze the unwanted apps rather than uninstalling them.  Titanium Backup and Link2SD can help you with that (both require root).  In ICS+, there's also a user-accessible mechanism to deactivate apps from the settings menu.