I'd indicate the date of the original (first) mail, and perhaps even those of the follow-up(s) instead of the -below-

Ich mach's immer so: Hoping you are back at work. In case my email of.... got caught up in the backlog, I attach the original. As the matter is quite pressing by now, I would appreciate an early reply. (etwas lang, aber damit kannste auf keinen Fall jemand auf die Fuesse treten)

I don't see too much wrong with what you've written. What I do think is always important in these cases is to take into account your relationship with the other person. If you're in a position of authority, you can probably take much more liberty. If it's someone you know well personally, you can take much more liberty. If it's a customer or your boss or whatever, you want to err on the side of caution.

btw, I think you're missing a comma between "office" and "I".

It seems a little impolite because of 'i would appreciate'. At the same time it only really implies impatience, which is kind of what you want to portray anyway, and certainly isn't rude.

Gute Idee, elk. Daß ich sowohl auf die Ursprungsmail als auch auf meinen ersten Nachhaker jeweils eine Abwesenheitsnotiz erhalten hab muß ich ihm ja nicht auf die Nase binden ;-)

Hab jetzt allerdings geschrieben "a reply at your earliest convenience" ;-)

So, die Endfassung (basierend auf elks Idee):

"I refer to my e-mails below which I fear got caught up in the backlog. As the matter is quite pressing by now, I would appreciate a reply at your earliest convenience"

yep, da kann er sich wirklich nicht beschweren. I hope he gets the message :-))

*As the matter is quite pressing by now*

'As the matter is now quite pressing' sounds better. 'By now' sounds a little awkward.

in this context..

Well, he needs something to smile about, doesn't he?

lol. fair enough ;)

This is always tricky - rude? I think not - after all, he/she hasn't responded in what - over a month? (although I guess in the rare case there may have been extenuating circumstances).
I would put "follow-up - urgent" in your subject line.
I would attach all previous emails regarding this matter.

Please find attached my previous emails. This matter has become quite urgent and I would appreciate your reply by November 9, 2007. Thank you for your prompt attention to this matter.

Sincerely,

PS - forget "at your earliest convenience" - fully meaningless IMHO - in his/her case, that could be next year

Sound aggressive? - I see it as normal business English under the circumstances :)

Just received his reply and apologies - in case you're interested ;-) Promised to give comments tomorrow.