Move and extrude axis locked?
Are you certain it is locked to the Z axis, and not the normal axis?
Both the normal and the Z axis have a blue color, so it is easy to mix them up.
You can see to which axis the extrusion is locked in the status bar while extruding.



You can change the axis the extrusion is locked to by pressing the key corresponding to the respective axis, so either one of X, Y or Z. 
Pressing one of these keys twice switches between global and local axis, pressing a third time removes all axis constraints during extrusion. 

If the selected face normals are not parallel or perpendicular to the global XYZ axii, you will not be able to align to the global XYZ-axis using middle mouse button, as that references the face's normals.  

It's also important to know that the default hotkey for extrude(E) will not 'just' extrude as it actually is 'Extrude and Move on Normals'. 
This means that, by default, it will always try to extrude along the normal axis of the selected face. 

If you want to change this behavior, you can change this in the settings. This will change the E hotkey to extrude without aligning to any axis, requiring you to set the axis yourself each time you extrude.

Blender 2.79 and older:
File > User Preferences > Input: Make sure the search bar is set to 'name' and search for 'extrude'. 
Under 'Mesh', there is the option 'Extrude and Move on Normals'. Expand that setting and change view3d.edit_mesh_extrude_move_normal to mesh.extrude_region_move. Click 'Save user settings' at the bottom of the window.
You can reset this value by clicking 'Restore' to the right of 'Mesh' in this same window if required.

Blender 2.80:
Edit > Preferences > Keymap:
Make sure the search bar is set to 'name' and search for 'Extrude'. Expand the option and change view3d.edit_mesh_extrude_move_normal to mesh.extrude_region_move.
You can reset this value by clicking 'Restore' to the right of 'Mesh' in this same window if required.