Personally, I use a pressure washer to clean the underside of the deck. You can turn the mower on its side and either use a pressure washer, or (as I did in pre-pressure washer days) use a gasket scraper or putty knife to scrape the underside of the deck. If you'd rather not turn the mower on its side, placing it up on two inverted 5 gallon pails should give you the clearance to get under there with your putty knife.
As for the starting problem, presuming this is a 120 volt plug in mower, a clogged deck could prevent starting. Short of that, be sure the plug is tight in the outlet and that there is power to the outlet.