When we talk about the big-O for a given problem, the default interpretation is for a deterministic computer. All of our existing deterministic algorithms for NP-complete problems are exponential, and solving an NP-complete problem like SAT on a non-deterministic computer is trivial (and not especially useful since we don't know how to build those).

A decision problem (i.e., determining whether a string is a member of some set) is in NP if there is a program and polynomials p and q such that for every string x in the set, there is some proof of that fact of size at most q(|x|), which the program can verify is correct in time at most p(|x|).

This implies that there exists an exponential-time deterministic algorithm to solve any NP problem: just check all the possible proofs, reporting "yes" if you find one that works, or "no" when you've generated all the proofs size q(|x|) and found that they fail.

Both. As I understand it, polynomial time in a non-deterministic machine can be simulated as exponential time in a deterministic machine