Something different:
Attributes[getMsgString] = HoldFirst;
getMsgString[x_] :=
Block[{MessagePacket =Return[ToString@ToExpression[#3[[1, 1, 3]]], Block] &}, x]
Now:
FindCycle[1, 2, 3, 4, 5] // getMsgString
"FindCycle called with 5 arguments; between 1 and 3 arguments are expected. >>"
To address the case raised the comments here is one approach:
flatFraction =
StringReplace[#,
Shortest["\\!\\(" ~~ n__ ~~ "\\/" ~~ d__ ~~ "\\)"] :> n ~~ "/" ~~ d] &;
getMsgString[x_] :=
Block[{MessagePacket =
Return[#3[[1, 1, 3]] // flatFraction // ToExpression // ToString, Block] &}, x]
500 / 0 // getMsgString
Infinite expression 1/0 encountered. >>
Incidentally I copied the string above using Plain Text. The direct output is:
"Infinite expression \[NoBreak]1/0\[NoBreak] encountered. \[RightSkeleton]"
If that is a problem additional processing can be applied; let me know if you need help with that.
Edit for more general case
Attributes[getMsgString] = HoldFirst;
getMsgString[x_] :=
Block[{MessagePacket =
Return[First[
FrontEndExecute[
FrontEnd`ExportPacket[
First[MathLink`CallFrontEnd[
FrontEnd`UndocumentedTestFEParserPacket[
ToExpression[#3[[1, 1, 3]]], False]]], "PlainText"]]],
Block] &}, x]
Examples

More MessagePacket
shenanigans:
Internal`HandlerBlock[{"MessageTextFilter", Print[{##}] &}, FindCycle[1, 2, 3, 4, 5]]
. The first argument to"MessageTextFilter"
gives the text. $\endgroup$