VMG is Nokia's format for storing SMS messages in. It is UCS-2 LE encoded. If you stop using Tie::File, and just open and readline the file like a normal person, then you can use Perl's IO layer to decode the UCS-2 LE encoding.

Supply an actual sample file and you might get more useful and complete answers.