Added 2 cases:

/*
         * Search for derivatives of link code <a href="mailto:email@example.org">
         * <img anything>email@example.org</a>
         */

and

/*
         * Search for derivatives of link code
         * <a href="mailto:email@amail.com?subject=Text"><img anything>email@amail.com</a>
         */

Test with

<p><a href="mailto:info@mysite.com"><img style="margin: 0px 3px 0px 0px; float:left; width:21px; height:21px;" title="Email to me" src="images/powered_by.png" alt="An email" width="21" height="21" />info@mysite.com</a><p>

and

<p><a href="mailto:info@mysite.com?subject= A subject"><img style="margin: 0px 3px 0px 0px; float:left; width:21px; height:21px;" title="Email to me" src="images/powered_by.png" alt="An email" width="21" height="21" />info@mysite.com</a><p>

Still broken but in a different way for me (Joomla 2.5.24)
HTML
https://www.dropbox.com/s/iqhz9xpo0t09v3t/Screenshot%202014-08-01%2009.19.12.png
Front end:
https://www.dropbox.com/s/frfpwycojgx3d5m/Screenshot%202014-08-01%2009.20.38.png
d

You can't test this on 2.5.
As it works fine on 3.3.3 (See tracker http://joomlacode.org/gf/project/joomla/tracker/?action=TrackerItemEdit&tracker_item_id=34020&start=0)
I merge.

Will test a modified #3967 on a 2.5

Test by replacing emailcloak.php in a 2.5.24 by this file:
http://info-graf.fr/ftpfolder/emailcloak.php.zip

Outputs invalid HTML:
https://www.dropbox.com/s/ws70w5ixmlja688/Screenshot%202014-08-02%2016.19.38.png
in browser:
https://www.dropbox.com/s/n3ll4is2yticezm/Screenshot%202014-08-02%2016.20.22.png
regards
d

What was, again, the original code used?
I tested with the codes I quoted here:
#4041 (comment)

and all is fine.

This is the HTML that renders with cloaking turned off.

<span class="contact email"><a href="mailto:info@redevolution.com"><img style="margin: 0px 5px 0px 0px; float: left; width: 27px; height: 27px;" title="Email Red Evolution" src="/images/stories/icons/social_icons/icon_email.png" alt="Email Red Evolution" width="27" height="27" /> info@redevolution.com</a></span>

thanks

d

Take off the space before the mail here:

height="27" /> info@redevolution.com</a>

and test with

height="27" />info@redevolution.com</a>

Solved. Many thanks.

I posted a new zip for 2.5.x (same url as above http://info-graf.fr/ftpfolder/emailcloak.php.zip ) which also adds these cases:
#4069 // that one is for 3.3.x
Thanks for testing on both

@test @infograf768 with

http://info-graf.fr/ftpfolder/emailcloak.php.zip

on a Joomla 2.5.24 successful.