This is probably not the answer you want, but:
Where I work we too were doing image URL rewrites to get larger versions of images in Facebook's RSS feeds. Because of the problem you're asking about, we ended up switching to using the FB Graph API to get our feeds (and images). We're getting larger images now, though the max size seems to be 480x480 and not a full 720x720.
To get your feeds through the FB Graph API you'll need to set up a Facebook app and get an access token for it. This tutorial (found through this answer by eric) gives an overview of the process of pulling a (page) feed; this tutorial (linked to from the first one) gives an in-depth, step-by-step walk through of setting up a Facebook app and getting an access token for it.
Note
The former tutorial gets a page's feed using a URL of the form:
https://graph.facebook.com/YOUR_PAGE_ID/posts?access_token=YOUR_ACCESS_TOKEN
At my company, we're using a feed URL of the form:
https://graph.facebook.com/v2.2/YOUR_FEED_ID/feed?access_token=YOUR_ACCESS_TOKEN
Note
If you don't want to enter your app's info into the second tutorial's page to get the app's access token then you can generate it yourself by making a simple URL call, as outlined in this answer by Avantaj Tvm. Do note the security concerns about using the token in the answer by CBroe.
When you get your access token in the form of:
access_token=YOUR_APP_ID|YOUR_APP_ACCESS_TOKEN
then you have to use that whole token (YOUR_APP_ID|YOUR_APP_ACCESS_TOKEN
), not just the YOUR_APP_ACCESS_TOKEN
part.
Edit
To get an even larger image you can do the following, as given in this answer:
For Graph API feed items which have a picture
, take the object_id
and construct the following URL:
https://graph.facebook.com/{OBJECT_ID}/picture
This is a direct download to the larger image.