Hi Michael,
It is a tough question and I don't think anyone has the definitive answer, least of all me!
Books such as Millard Erickson's 'How then shall they be saved?' outline the different views on this topic if you are interested.
Here are a some hurried thoughts from my own struggle with this question:
1. I think it is necessary to recognize that there is an asymmetrical nature to this question, namely:
a. We are saved through faith in Christ.
b. But we are condemned because of our sin, and because of our sin alone, not because we haven't heard (see Ephesians and Romans).
Too often we take a dualistic world view where everything is in black and white, in symmetrical opposition. (Actually, it seems to be a predominantly western world view influenced by those old Greeks). I have found that as I study the word, this is not the case with God. Sure there is good and evil, but good is ontological, evil is not, and so God will destroy it (...has destroyed it through Christ's work on the cross).
Sure there is life and death but life, swallows up death! (1 Cor 15).
Sure God saves by His grace, but we condemn ourselves by our sin. It's the divine sovereignty vs human responsibility tension again which we all struggle with.
2. I think it is tempting, as others have pointed out, to sentimentalise God ("Is this a merciful God?" type questions). We find it hard to accept God's wrath as an aspect of His love, yes, His love! I could go on about this a bit, but you have probably heard this before. If not, a useful book there would be D.A.Carson's "The difficult doctrine of the love of God".
When I find myself asking questions like "Is this the sign of a merciful God?", I try to ask myself (and God) - is this who God says He is, who He reveals Himself to be in His word, or is this my own 'nice genie' notion of God?
If it's a 'nice genie' notion, I ask myself why I hold it and why am I so scared to discard it in favour of God's truth about Himself. Sometimes it's because it is something I have been taught or held to for a long time and haven't really questioned before. Sometimes I prefer a 'nice genie' notion because the truth confronts some matter of disobedience or pride in me, or requires change in some aspect of my life that I do not want to submit to God.

Sometimes it's because I am taking an worldy point of view instead of God's point of view - my underlying presuppositions are upside down and the wrong way around. Sometimes it's because I don't want to appear hard-nosed, hard-lined or something of that nature amongst my friends or I am too afraid that if I tell my unsaved friends about God, they will reject Him. You know, all the wrong reasons for holding to false notions of God! And sometimes it's because I just well want to know how and why, right here, right now. *stomp foot*
3. As for you, I think you already have the answer. You KNOW God to be holy, merciful and just. He demonstrated that most clearly when Jesus died for us on the cross,in accordance with God's promises, WHILE WE WERE STILL HIS ENEMIES AND HATED GOD. So while we may not have the definitive answer on this one, we can rest assured that his actions and judgments are true. And one day, both those who are saved and those who are condemned will bow the knee in acknowledgement of that fact.
artofstone