I can confirm that scenario 1 does happen with 3.5.1.
I cannot however confirm that scenario 2 happens in 3.5.1. This probably has something to do with how your Focus Policy is set up so I need more information on how you've configured that. 
I'll hold off on the kde 3.5.2 update (to confirm the actual report) until I get this information.

I am sure that the scenario1 bug was not present in kde 3.5.1. I might be
wrong, but I remember having the behaviour on kde 3.5.1. Since that is what I
have used for comparison. Anyway, someone on kde 3.5.1 please confirm.

I am attaching a screen shot of my focus settings, mostly default. And as I
said, the problem exists on new freshly created user too.

Created an attachment (id=15447) [details]
Focus policy settings

Please tell if any more info is needed.

ok, there seems to be some confusion caused by my comments. I'll attempt to
clarify.
I can confirm that the _Expected Behavior_ listed in Scenario 1, does in fact
occur for 3.5.1. 
I can NOT confirm that the _Expected Behavior_ listed in Scenario 2, occurs for
3.5.1.

Created an attachment (id=15448) [details]
Focus stealing prevention settings

As requested by illogical. Note : the problem is prevalent even when the level
is set from "Low" to "Normal". I have not tried higher levels.

OK, I can now confirm the Expected Behavior for Scenario 2, when KDE 3.5.1's
focus stealing prevention level is set to "High". If set to anything lower in
3.5.1 the new ~ konq window gains focus in which case an ALT+TAB will just
switch *away* from it).

Yes, in simple words, the point is - 
1) Minimized windows must be in the absolute bottom when the alt-tab window list is shown, so as not to navigate to it and

2) Urgent requesting windows must be in the absolute top, so that the next time I press alt-tab that window must get activated.

I've confirmed this on 3.5.2. So this change in behavior was introduced between
3.5.1 and 3.5.2.
It also applies to KDE windows (not firefx specific) 

Yes, it is not firefox specific. Its just that I use that type of scenario
mentioned above, frequently. Also, if this is meant as a new "feature" of kde
3.5.2, please change this to a "wishlist" request to revert the change.

I am told that this problem does not occur on debian. I am looking at --
http://ftp.debian.org/debian/pool/main/k/kdebase/kdebase_3.5.2-1.diff.gz -- but
I cant find any patch that fixes the kwin problem, can someone please look ? I
will try some more hunting, in any case :)

*** Bug 125093 has been marked as a duplicate of this bug. ***

SVN commit 528629 by lunakl:

Move minimized windows to the right place in focus chain.
BUG: 124807



 M  +1 -1      activation.cpp  
 M  +4 -3      client.cpp  
 M  +1 -1      events.cpp  
 M  +21 -7     workspace.cpp  
 M  +2 -1      workspace.h  


--- branches/KDE/3.5/kdebase/kwin/activation.cpp #528628:528629
@@ -231,7 +231,7 @@
         last_active_client = active_client;
     if ( active_client ) 
         {
-        updateFocusChains( active_client, true ); // make it first in focus chain
+        updateFocusChains( active_client, FocusChainMakeFirst );
         active_client->demandAttention( false );
         }
     pending_take_activity = NULL;
--- branches/KDE/3.5/kdebase/kwin/client.cpp #528628:528629
@@ -578,7 +578,7 @@
     updateAllowedActions();
     workspace()->updateMinimizedOfTransients( this );
     updateWindowRules();
-    workspace()->updateFocusChains( this, false ); // make it last in the focus chain
+    workspace()->updateFocusChains( this, Workspace::FocusChainMakeLast );
     }
 
 void Client::unminimize( bool avoid_animation )
@@ -1158,7 +1158,8 @@
     info->setState( b?NET::SkipTaskbar:0, NET::SkipTaskbar );
     updateWindowRules();
     if( was_wants_tab_focus != wantsTabFocus())
-        workspace()->updateFocusChains( this, isActive());
+        workspace()->updateFocusChains( this,
+            isActive() ? Workspace::FocusChainMakeFirst : Workspace::FocusChainUpdate );
     }
 
 void Client::setSkipPager( bool b )
@@ -1200,7 +1201,7 @@
         }
     if( decoration != NULL )
         decoration->desktopChange();
-    workspace()->updateFocusChains( this, true );
+    workspace()->updateFocusChains( this, Workspace::FocusChainMakeFirst );
     updateVisibility();
     updateWindowRules();
     }
--- branches/KDE/3.5/kdebase/kwin/events.cpp #528628:528629
@@ -370,7 +370,7 @@
             if( c )
                 {
                 c->windowEvent( e );
-                updateFocusChains( c, true );
+                updateFocusChains( c, FocusChainUpdate );
                 return true;
                 }
             break;
--- branches/KDE/3.5/kdebase/kwin/workspace.cpp #528628:528629
@@ -512,7 +512,7 @@
         }
     else
         {
-        updateFocusChains( c, false ); // add to focus chain if not already there
+        updateFocusChains( c, FocusChainUpdate ); // add to focus chain if not already there
         clients.append( c );
         }
     if( !unconstrained_stacking_order.contains( c ))
@@ -591,7 +591,7 @@
     updateClientArea();
     }
 
-void Workspace::updateFocusChains( Client* c, bool make_first )
+void Workspace::updateFocusChains( Client* c, FocusChainChange change )
     {
     if( !c->wantsTabFocus()) // doesn't want tab focus, remove
         {
@@ -605,11 +605,15 @@
     if(c->desktop() == NET::OnAllDesktops)
         { //now on all desktops, add it to focus_chains it is not already in
         for( int i=1; i<= numberOfDesktops(); i++)
-            { // make_first works only on current desktop, don't affect all desktops
-            if( make_first && i == currentDesktop())
+            { // making first/last works only on current desktop, don't affect all desktops
+            if( i == currentDesktop()
+                && ( change == FocusChainMakeFirst || change == FocusChainMakeLast ))
                 {
                 focus_chain[ i ].remove( c );
-                focus_chain[ i ].append( c );
+                if( change == FocusChainMakeFirst )
+                    focus_chain[ i ].append( c );
+                else
+                    focus_chain[ i ].prepend( c );
                 }
             else if( !focus_chain[ i ].contains( c ))
                 focus_chain[ i ].prepend( c ); // otherwise add as the last one
@@ -621,11 +625,16 @@
             {
             if( i == c->desktop())
                 {
-                if( make_first )
+                if( change == FocusChainMakeFirst )
                     {
                     focus_chain[ i ].remove( c );
                     focus_chain[ i ].append( c );
                     }
+                else if( change == FocusChainMakeLast )
+                    {
+                    focus_chain[ i ].remove( c );
+                    focus_chain[ i ].prepend( c );
+                    }
                 else if( !focus_chain[ i ].contains( c ))
                     focus_chain[ i ].prepend( c );
                 }
@@ -633,11 +642,16 @@
                 focus_chain[ i ].remove( c );
             }
         }
-    if( make_first )
+    if( change == FocusChainMakeFirst )
         {
         global_focus_chain.remove( c );
         global_focus_chain.append( c );
         }
+    else if( change == FocusChainMakeLast )
+        {
+        global_focus_chain.remove( c );
+        global_focus_chain.prepend( c );
+        }
     else if( !global_focus_chain.contains( c ))
         global_focus_chain.prepend( c );
     }
--- branches/KDE/3.5/kdebase/kwin/workspace.h #528628:528629
@@ -251,7 +251,8 @@
         bool checkStartupNotification( Window w, KStartupInfoId& id, KStartupInfoData& data );
 
         void focusToNull(); // SELI public?
-        void updateFocusChains( Client* c, bool make_first );
+        enum FocusChainChange { FocusChainMakeFirst, FocusChainMakeLast, FocusChainUpdate };
+        void updateFocusChains( Client* c, FocusChainChange change );
         
         bool forcedGlobalMouseGrab() const;
         void clientShortcutUpdated( Client* c );

Thanks for fixing it so fast ! :)

*** Bug 125797 has been marked as a duplicate of this bug. ***

Just for the record, I have filed a wishlist on debian as well as ubuntu to
request merge of this patch in kdebase. Links:

http://bugs.debian.org/363357
https://launchpad.net/bugs/40089

Also, talked to the frugalware developer, he will most probably be rebuilding
the kdebase package, incorporating this patch.