I'm trying to understand what mistake I'm making or what incorrect information I fail to recognize as such.
The subset sum problem (given distinct $a_i$ and $A$, does any subset of ${ a_i }$ sum to $A$?) is NP-complete. However, integer relations (given the same $a_i$, are there integer $c_i$ below a fixed but arbitrarily large bound such that $\Sigma c_i a_i = A$?) can be solved, both as decisional problem and as answer-finding problem, efficiently (in polynomial time in the size of the inputs), e.g. by PSLQ.
This seems to be a contradiction to me: If the subset sum problem has a solution, PSLQ should find it in polynomial time. And if it does not, PSLQ should report this in polynomial time. But if that were true, the subset sum problem would be solvable in polynomial time and hence would be in P.
So what am I missing?
The problem you've described is usually known as subset sum, which can be thought of as a special case of the knapsack problem where the weights and values are equal for each item and the weight and value limits are also the same.
PSLQ cannot solve these problems in polynomial time because the arithmetic operations that it performs (repeatedly squaring and dividing the terms) cause an exponential blowup in the size of the inputs. Unfortunately, exponentially sized data requires exponential time to store and manipulate, otherwise NP-complete problems would indeed be decidable in polynomial time.