I think mail and OpenVPN should be fine... looking at the Freedombone site
you linked to seems to confirm that as well. I don't know about any
self-hosted search engines except that I've heard of Yacy which seems cool
but I remember hearing an interview with the developer saying that they
couldn't getting running on 512mb of ram
You probably would need to use some sort of flash memory, if only just for
booting... I am pretty sure you can only boot off of the SD card or the
internal flash. You might find this guide useful if you want to use an
external drive (it is about raspberry pi but the steps should be pretty
similar for BBB)
https://learn.adafruit.com/external-drive-as-raspberry-pi-root/overview