You might try using -all instead of ~all there is a lot of discussion as to what to use here. I think -all is the better solution because it basically says "Only the IPs and entities in this SPF record are allowed to send mail from this domain". Whereas ~all says "The IPs and entities listed in this SPF record are probably the only servers that will send mail from this domain". -all is just a little more strict.
You also don't need to include gmail.com, yahoo.com, and hotmail.com unless you are sending mail from orange.com from these servers.
Also how are you sending these messages? Make sure the envelope sender of these messages is using the orange.com domain. This problem is typical if you are using PHP or a CGI script to send out these messages. The envelope-sender might be set to the server's hostname.
You should also bear in mind that I don't think a lot of mail providers use SPF as the be all, end all, of determining a message's spam worth. It is just used to weigh the message. The sender server and SPF record may match, but if the message still contains a lot of spam words and spam like identifiers, it can still be flagged as spam.
If you are sending out mail from orange.com only from this specific server (i.e. your not using your ISP or any other mail server to send out mail from orange.com) then yes this should work.
Keep in mind that this is a DNS change and DNS changes may take a few hours to fully propagate, so don't expect instant changes with the spam weighing of your message. Also, the issue with your message being flagged as spam might be due to other factors other than the SPF record.
Says that the only IPs that should ever send legitimate messages from orange.com are the A records for orange.com and the MX records for orange.com
In the example you give at the start of the message, you show that the A record for orange.com resolves to 22.214.171.124. The MX record for orange.com is set to mail.mysite.com. What IP address does mail.mysite.com resolve to?
mail.mysite.com and orange.com are probably on the same server then. This probably doesn't really matter. It basically comes down to what the sending IP is of the server that is sending messages out from orange.com. Is one of these IPs the IP address of that server?