The only recommendation I can give you is to search again. You cannot delete the stock Photo icon (the one that Apple "gives" you with your new iPad).
Maybe it's just, somehow, moved to another page? Just keep swiping.
Or, who knows, maybe your iPad's having a bad day. Have you tried a reboot (hold both the sleep button and the home button down until the screen goes dark and then the white apple icon shows)? That's been known to help a lot of iPad quirky behavior...
Sorry, but that's all I got for you.