No, it must work with non-fixed fonts too.
I'll implement the second system I posted, but you gave me an idea for improving the number of guesses, maybe.
Just measure the size of an average letter (char a?), and then instead of starting the search in the middle of the string, start at the index of the result of dividing Label.Width / char's width.
I think that could very much improve performance with very long strings, since I must repeat that process for every line, inserting CRLF on the cutoffs until I fill all the text in the label...