The cleaners you mentioned are generally safe to use and should have been able to remove normal food soil. It sounds like you have something that is particularly stubborn and/or has baked onto the oven over time.
The next thing to try would be ammonia, but be careful because it's caustic and noxious. An aerosol lye spray oven cleaner would be even more powerful, but also more hazardous, so use that only as a last resort.
Take care to avoid skin contact with these cleaners, and don't breathe in their fumes!
Once you've thoroughly cleaned your microwave, it will stay clean if you take care to cover food while cooking. When splatters do occur, they're much easier to remove if cleaned up immediately. Otherwise, the splattered food hardens and the stains get baked on.