Speaking as a dealer tech....One of the goods ones i might add...Heres
some questions i have for you sure it may be a passlock issue....(Theft)
But what are some of  the things they replaced, do you know what codes
if any it had?  Pass lock it one of them things low voltage can
trip....If i knew the  codes  could save you alot of money and tell you
how to fix it yourself...The theft on your car will most of the times
start then cut right off..How many miles are on it ?I cam give you any
info you need if you can give me somemore information..
S Cook
1998 Malibu Starting Problem  

Group: alt.autos.chevrolet.malibu Date: Mon, May 16, 2005, 5:35pm
(CDT+1) From: UseLinkToEmail@AutoForumz.com (Dagen)
My 1998 Chevy Malibu has problems starting which have just started in
the last few months and are getting worse. It can happen when it is cold
but also when it is warmed up. You have to crank it many times,
sometimes for 10+ minutes, to get it to turn over.
The dealer has changed many parts and the problem has not improved. A
local repair shop suggested that it may be the anti-theft device.
Does anyone have any experience with this problem? What could we suggest
the dealer look at since they don't seem to have any idea?