Well, I basically play the same like you guys: do all the side missions (except the three with time limit, no thanks) than move on. Problem is that you are than overpowered for the story mission and don't get EXP for killing (only 1 EXP).
It is exactly the calculation Shifty presented that I fear: getting 1EXP, killing 100 gives you 100EXP plus the mission bonus EXP. Maybe the EXP is somehow broken and you need to do it in the right order.
Problem is, even though killing enemies with 1EXP or say the larger ones with 10EXP: you often cannot rush, because the can still kill you rather quickly. That is why I often think that EXP downgrading is to aggressive in BL2.
An example: I played 3h yesterday. Was level 31. I did three side missions in a new area, basically cleared that area. The mission lvl was 28, 29 and 29. Killing enemies gave me 100 - 200 EXP. So this was ok. Mission bonus was about 15k EXP total. But with all this, it took me the whole 3h to reach lvl 32, with constant fighting and killing. Furthermore did the lost treasure quest...after an hour, lame loot as hell: three green grenade mods
I have now 55h put into the game, am at lvl 32. So in average more than an hour per lvl. But this will increase quickly when I need 3h for each new lvl.
Despite all this: game is amazing, one of the best out there. Game keeps delivering new missions and areas...amazing. One of my favorite games so far!
I used my shotgun yesterday the first time, as I wanted to save me my sniper ammo for the long journey. I somehow looted a purple one, ages ago with 345 x 17 damage. Its called Social Crowdsourcing or something like this...and it is surprisingly my absolute best gun?? Way better than my snipers! It just rips everything apart, even in mid range! I found myself running around like a flak monkey, using snipers only for far away copters. Crazy!
Today, I go for the story mission...which is unfortunately lvl 25...