Always got a chuckle when Canadian tourists would take pictures of Tim Hortons written in Arabic: http://cdn.torontolife.com/wp-content/uploads/2012/11/tim-ho...

I prefer to write Tim Hortons like this "تِم هُرتُنز" in Arabic but that's just me.

Aside from that, Spanish, Catalan, and Occitan have historically been written using both the Arabic and Hebrew alphabets, by their respective user communities. Same for Yiddish, linguistically a Germanic language, which was often written using Hebrew script. Turkish seems to flip from Arabic to Latin and vice-versa every few decades.

English written in Arabic script looks surprisingly natural to me.

Is there a simple algorithm for Latin letters to Arabic ones (meaning logic input letters, not shaped ones)? Or are there lots of complexities? My understanding of the Arabic language is that most vowels are omitted in writing, but that might be wrong.

It would have to depend on what language you're trying to transliterate, because the phonetic meaning of the Latin letters is different depending on the language they're used to represent (and for many languages, depending on the particular word). For example, ti- will usually be /tʃi/ in Brazilian Portuguese and /tɪ/ in English. Typically each orthography is specific to a language and a script doesn't encode sounds in a consistent language-independent way, so you have to know something about both the source and target languages to devise a transliteration system.