What exactly are we talking here--poured concrete floor? Concrete block walls (like a basement bedroom)?
If you're talking concrete walls--either poured or block--that surface is likely quite porus. Could be that the sealer you used wasn't able to adequately bridge the gaps to fill those pores so odor down in the concrete is still getting out. Any shellac I've worked with has been pretty thin consistency, and IIRC is mostly alcohol that evaporates away (low solids) which would be inherently bad at bridging big pores.
If what used was truly a shellac (and you haven't painted over the top) subsequent coats should "melt in" without any issues. Perhaps go back with another wetter/thicker coat of the same stuff, or use something different that is inherently better at dealing with big pores.
You would probably want do some research, but I think most finishes can be applied over top of shellac so if you try something else you may not necessarily have to strip the old stuff off. Something like the oil-based version of Kilz might be worth a shot.
I don't see how grinding is going to gain you much... it sounds to me like the urine is soaked down into the concrete and your problem is that you didn't achieve a good seal to keep it from coming out.