A lot of Ultras are completely invulnerable indeed, but only at the very start. For example, as a rough guess Ibuki Ultra 2 is invulnerable only for the 2-3 first frames but it becomes active only at frame 9. You got a whole 6-7 frames of vulnerability in there. Also, it means you can trade in the ultra (double hits). Let's assume the invulnerability only lasts 2 frames. Normal grabs start in 3 frames. So if you throw in the Ultra in grab range and Zangief reacts by doing a grab during the animation, he'll catch you at frame 3, after your invulnerability ended and before you landed the first hit, thus you lost.
To your question, I'd say that in a single frame, the game first checks if grabs connect, then if hits connect. If both players hit at the same time, well then, they do get hit at the same time which allows you to do draws and the like. But most of the time the question on who hits who is decided by who hits first at the frame level since double hits aren't that common.