Weird problems with collision in Super Heli Land

[Darkhog]

I thought this'd be most appropriate board to ask. I have fixed crashes (and hopefully there won't be more for a time), but now I have more mundane and less critical problem, namely shaking (and occasional stuck) in collision detection.

To reproduce and help debug me issue, clone my git repository: https://github.com/darkhog/SuperHeliLand and follow instructions found in COMPILING.txt

You'll need to get to debug mode (right CTRL+left Shift+D) and then collide into other Marine Pop (submarine) to see it.

Here's the code that handles movement and reacting to collisions:

//movement  if al_key[Options.binding_up]<>0 then begin MarioGO.y:=MarioGO.y-4; lastup:=true; end;
  if al_key[Options.binding_down]<>0 then begin MarioGO.y:=MarioGO.y+4; lastdown:=true; end;
  if al_key[Options.binding_left]<>0 then begin MarioGO.x:=MarioGO.x-4; lastleft:=true; end;
  if al_key[Options.binding_right]<>0 then begin MarioGO.x:=MarioGO.x+4; lastright:=true; end;


  //reacting to collisions;
  if ((MarioGO.isColliding(OtherMarioGO)) and (lastup)) then MarioGO.y:=MarioGO.y+8;
  if ((MarioGO.isColliding(OtherMarioGO)) and (lastdown)) then MarioGO.y:=MarioGO.y-8;
  if ((MarioGO.isColliding(OtherMarioGO)) and (lastleft)) then MarioGO.x:=MarioGO.x+8;
  if ((MarioGO.isColliding(OtherMarioGO)) and (lastright)) then MarioGO.x:=MarioGO.x-8;


  //if ESC was pressed, return to main menu
  if al_key[AL_KEY_ESC]<>0 then CurrentState:=MainMenuState;
  inherited Update;

All of it is in TDebugState.Update (States unit).
Problem is that when I'm trying to subtract/add in reacting to collisions phase exact same amount that was added to position in movement phase, object get stuck and can't get out of it by other means than going sideways if that was collision from top/bottom or by moving vertically, if I was moved horizontally when collision occurred. When I'm subtract 8 instead of 4, I get object shaking, like it has epilepsy. What gives?

Can someone help me debug that issue? I also can't move object by smaller/bigger amount that 4 as my game is scaled up and single pixel is 4x4 square on screen and as you know, it'd look weird if character can move by half of pixel.

//edit: Blue square that sometimes pops on screen means that collision between both objects has been detected. Collision itself is fine, just reaction to it is not.