I developed a Visualforce emailtemplate and used all the custom labels to translate into different languages. the subject is coming as ??????? for all the languages except for english, but in preview i can able to see the subject in translated language .we are using the outlook as the mail-box.
https://help.salesforce.com/apex/HTViewSolution?id=000005102&language=en_US Check encoding, Go to your template -> Edit -> Encoding -> select Unicode (UTF-8) It has to work.