I don't think there is any real solution for this, I suppose you must be pretty big to actually have it be noticeable enough to be a problem, either that or you have users that change emails a lot and forgot their addresses.
So what I would do is multiple things:
1. when signing up suggest you will send them monthly notices. Probably you won't be allowed to by a lot of users but at least you tried.
2. the monthly notice has an image with unique id in it, if that image gets requested you know they have looked at mail and then they still have that address. if not you know to flash them a message next time they come in - have you changed email recently? If they have they are logged in currently so can go change email.
---2
User clicks forgot password
Please write email
writes email
We do not have a record of that email, have you lately changed email.
Yes I have.
We have a credit card on record with us, is the one we have on record still the one you use
yes
Pay 1 dollar (refundable or not depends on stuff) to unlock account. Make sure to use the credit card we have on record!
Check the credit card used is the same you have on record. See credit card validates. Obviously people can have stolen credit card, you know if your service or the people you serve would be likely to have this kind of thing happen to them.
----3
What kind of stuff does one do in your service, is it unique enough that one can ask name an X that you did recently and the user would be able to describe well enough that you could then find it, when finding it then present 6 example cases one of which is the one they described others generated to resemble it, and then they have to say which one they actually did. Question is if this part is automatable, many services would not be able to automate this kind of thing.