Why does this pattern ‘a.\{-}p\@!’ not match?

”\{-}” doesn’t just mean “as few as possible”, it means “as few as possible to make the whole pattern succeed”. If it didn’t match the ‘p’, the whole pattern would fail (because of the “p\@!”) so it does match the “p”. It is a longer match, but it is the shortest match that makes the whole pattern succeed. If you wanted “as few as possible regardless” you would use “\@>”, which basically divides a pattern up so that the pieces either side behave independently. If the pattern were “a.\{-}\@>p\@!” then “.\{-}” would always match nothing because that’s the smallest match that can succeed when there are not other restrictions. The whole pattern then would behave the same as “ap\@!”, i.e. it would match any “a” not followed by a “p”). This means, it matches as few as possible ‘a’s without trying to keep going until Vim finds the longest match. This means, it will still match ‘ap’.