Arduino pulse counting & storing
A 99% workable solution likely lies somewhere between the absolutes.  For example:

You could transmit an incrementing count.  The receiver can miss some transmissions as long as it gets a later one.  If it gets a later transmission re-starting from (near) zero, it can assume the transmitter has been power cycled and can add the historically received count to the new one.  You could measure the time duration of any gap and estimate the number of missed counts during the power loss based on either the rate before the loss or from a past period that might plausibly be similar (ie, same time of same day in preceding few weeks, or from a few weeks period a year ago, etc).  This may work even better if you make the correction after the fact to equalize consumption over longer periods (ie, outage of a few hours, fix the total for the day to match similar days, rather than the hour to match similar hours).  Also consider that the fact of a power outage may alter behavior and thus gas/water usage.

You could periodically store the count value to EEPROM, if you do it at nice round numbers you could do so using relatively few bits since you would only need the significant ones.  Upon power cycle, you could restart the count at the last saved number.  The receiver would see the count resume at a slightly lower number than before, and could add the difference back in to the received numbers.

As most power outages are short (some recent exceptions aside) you could use battery backup.

If the meters have a display, you could take an entirely different approach and point a camera at them and use optical character recognition on the images.

No system is perfect - in extreme cases, intelligent manual correction may be needed.