You need to look in your "Purchased" apps section of the App Store. You can not find SkySafari 3/4 through search anymore.

Also, you must be logged in using the same iTunes account that was used to purchase the app in the first place.