Можно ли записать программу на флешку и запускать ее не устанавливая на комп? Если да, то не оставит ли она следов в реестре?

Если прога портабельная, то да. Как проверить? Установи прогу как положено, потом скопируй папку c ней из Program Files на флешку или другой диск, удали установленную, и попробуй запустить скопированную.
Проверь, все ли функции рабочие. Если устраивает, то пользуй на здоровье.
Следы в реестре останутся. Прога распакует кое чего во временную папку. В реестре будет на неё ссылка.

Все программы с http://softlab-portable.ru/ можно запускать с внешних
носителей и в реестре они не прописываются потому что portable.

Зависит от конкретной программы. Есть те, которые оставляют, а есть те, которые не используют реестр.

softlab-portable.ru не рекомендую, потому что это рассадник пиратских программ. Рекомендую http://portableapps.com/apps , потому что там только программы с ненарушенной лицензией.

Для ознакомления:
http://ru.wikipedia.org/wiki/Переносимое_приложение
http://en.wikipedia.org/wiki/Portable_application

Можно и не оставит, я так делаю только с жесткого внешнего диска.