While @bowesmana 's solution should work be aware that working with structured data using just regexes can lead to unforeseen problems.
Try this
| rex mode=sed "s/(<Message>).*( is pending)(<\/Message>)/\1request\2\3/"