First off, it's useful to be able to determine any reductions. In particular, your subqueries can be removed:
AND date_move >= '2013-09-01'
AND store_id NOT IN(SELECT store_id
FROM storage_availability
WHERE date_move <= '2014-04-30')
actually reduces to:
AND date_move >= '2014-05-01'
(well, the intermediate step would be AND date_move > '2014-04-30'
, but you want to avoid that in the case that something is a timestamp or similar)
The needed query is then:
SELECT store_id, availability_before, date_move, availability_after
FROM storage_availability
WHERE (availability_before >= 2000 AND date_move >= '2014-05-01')
OR (availability_after >= 2000 AND date_move < '2013-09-01')
OR (availability_after >= 2000 AND availability_before >= 2000
AND date_move >= '2013-09-01' AND date_move < '2014-05-01')
which yields the required:
STORE_ID AVAILABILITY_BEFORE DATE_MOVE AVAILABILITY_AFTER
1 2500 '2014-06-01' 3500
3 8500 '2014-07-15' 1000
4 3000 '2013-11-01' 2000
(and working fiddle)
Interestingly, given the answer to this question, I suspect that there may be some logical reduction available, but I'm not seeing it at the moment. The ones I am seeing aren't really any good...