I was assuming that the values between the { } characters never contain newlines. I don't see why they should.
If this is true, then the following should work.
Code:
lines = text.split('\n')
result = []
for l in lines:
result.append(composite_formatter.safe_format(l, mi, 'XXX', mi))
val = '\n'.join(result)
This code gives you back the multiline text, with template fields inserted.
Am I missing something?