Sorry it wasn't the answer. You should try to provide an example of the data you are searching for as well as the code -- that is, the subject line itself. If we can't see it, we can't rule out that the method is properly returning no results due to your search string correctly not matching. Perhaps the subject line contains control characters or such? The relevant docs might provide more insight as well. I'd try a few more variations myself ...
UPDATE!
Did you try removing that final, trailing double quote?
my @uids = $imap->search( 'SUBJECT "test email "abc123" approved' );
