best way of replacing all tags in a string with java

I have a service method that takes a String and then replaces tags in the String with items from a tag library. As follows:

for( MetaDataDTO tag : tagValues )
{
    message = message.replace( tag.getKey(), tag.getText1() );
}

Obviously; this make heaps of new strings and is BAD. But the StringBuilder replace method is cumbersome to use for multiple strings inside one string. How can I make my method more efficient?

It is for use with blocks of text such as:

Dear #firstName#, your application for #applicationType# has been #approvedRejected# sorry.

Where #firstName#, etc are the keys in a meta data database. It is also possible that tags may not be surrounded by hash characters.

Thanks for your help guys. Certainly learned more about java. Here is my solution. It is this way to support different looking tags and tags within tags:

private static String replaceAllTags(String message, Map< String, String > tags)
{
    StringBuilder sb = new StringBuilder( message );
    boolean tagFound = false;
    /**
     * prevent endless circular text replacement loops
     */
    long recurrancyChecker = 5000;

    do
    {
        tagFound = false;
        Iterator it = tags.entrySet().iterator();
        while( it.hasNext() )
        {
            Map.Entry pairs = (Map.Entry) it.next();

            int start = sb.indexOf( pairs.getKey().toString() );

            while( start > -1 && --recurrancyChecker > 0 )
            {
                int length = pairs.getKey().toString().length();
                sb.replace( start, start + length, pairs.getValue().toString() );
                start = sb.indexOf( pairs.getKey().toString() );
                tagFound = true;
            }
        }
    }
    while( tagFound && --recurrancyChecker > 0 );
    return sb.toString();
}