I suggest that if you want anything near the airport you might be able to try to contact some of the local hotels. A quick Google search has turned up s site called bounce which has a couple of places in Jeddah city offering $5.90 a day a bag for storage. This is just the result of a search and it's not a recommendation. If I were to search in Arabic there might be more. With this being a common pattern of travel to Saudi you would imagine there must be some local businesses offering storage services, perhaps websites or forums that discuss the activities you are likely to do in Saudi are more likely to yield results?