Thanks for these suggestions, I got both to work, and in case anyone is wanting an answer for this later on, this is the code I came up with:

DeleteZeroColumns:=proc(M)
local i, P, L;     
P:=M;
L:=Reverse([SearchAll(0,convert(P(1,1..3000),list))]):
for i in L do
    P:=DeleteColumn(P,i);
end do:
P;
end proc:

The second one is

DeleteZeroColumns:=proc(M)
local i, P, AS, ASC;      
P:=M;
AS:=ArrayTools:-Size(PP)[2];
for i from 1 to AS do
    ASC:=ArrayTools:-Size(P)[2];
    if P(1,ASC)=0 then
        P:=DeleteColumn(P,ASC);
    end if;
end do: # This deletes the zero columns at the back first

AS:=ArrayTools:-Size(P)[2]:
for i from 1 to AS do
    if i<ArrayTools:-Size(P)[2] then
        while P(1,i)=0 do
            P:=DeleteColumn(P,i);
        end do;
    end if;
end do; # This deletes the zero columns before the end
PP;
end proc:

They both work, and run at about 1 second each on my machine. Once again, thanks for the advice!