PuzzleManiak €3.99 – includes a lot of Nikoli puzzle games (in fact most of the ones from here are in there), all are randomly generated with different difficulty levels and includes a daily Web Challenge where you compete against other’s times. Worth it alone for Slitherlink.
Vexed €0.79 – Good port of the Palm OS game including all level-packs.
I’m still looking for a version of Sherlock (Windows) or Hercule (Palm OS) for the iPhone…