So big-O implies that the runtime is "dominated" by the term in brackets, or put another way, if I say something is O(n^2) I'm stating that as n->infinity the runtime of the algorithm |R| <= c * n^2, where c is some constant.

This is still true of exp^n, since |R| <= cn^2 <= dexp^n. Or at least based on my analysis background I'd expect this behaviour. It is of course a little pointless to say the algorithm is O(exp^n), but that's a different issue. It is still an asymptotic upper bound.

I just checked my copy of Sipser. Example 7.3 on page 249 if you care. They give an example that f_1 is O(n^3) and state it is O(n^4) also, since n^4 is also an (asymptotic bound) bound.

But this is not the point. I have no formal computer science education at all (my background is mathematics, some logic if that counts, but I've never studied algorithms) but many interviewers insist on this one specific area of CS, and yet if you attempt to engage them on the meaning of the things then unless you are very lucky they will a) make some excuse about how they'd have to check, their degree is a while ago, or b) they're actually only reciting also.

I'm strongly of the view this is a massively cargo-culted interview question of questionable to no value for most software engineering jobs, given that interview time is very limited and there are many more important factors to evaluate.