Howdy.

I'll be in the UAE for about 10 days. Decided to take a side trip to Oman.

I have a return flight from Muscat to Dubai that gets me to Dubai about 4 hours before my final flight back to the USA. Different airlines, totally unrelated reservations (FlyDubai + KLM).

My question: Will I have to go all the way through Dubai customs to get my checked bag or is there a way to get my checked bag onto my KLM flight without any hassel?

Thanks!

Did you try looking at the FlyDubai website?
The transfer protocols (including baggage) are pretty clearly laid out http://www.flydubai.com/en/plan/connections/

Thanks! I looked around and never found that. Everything I need. Cheers.

I did this before - I was on a FlyDubai DOH-DXB and then a Jet Airways DXB-BOM.

Yes, there is a service that will interline your bags for you without having to clear immigration and security and re-check them. However, if you have a visa or are eligible for visa-free entry into UAE, I would definitely NOT use this service or go this route. Here is a summary of my experience:

1. You arrive in the budget terminal via a bus from the fly Dubai flight and it is jam packed with people. I am talking 3rd would citizens sitting on the floor wherever there is space.
2. On the right, there is a desk and a line for a 3rd party company that handles the baggage transfer for you. No people to greet or help you, so it is hit or miss that you go to the right desk and wait in the right line. Give all your flight information to them and they will give you a receipt for the transfer (didn't cost me any $$).
3. You then go over to another counter behind a security check towards the left and hand them the receipt and tickets that the 3rd party company gave you and they do some crunching and give you another receipt of some kind.
4. Then there is a little security check that you need to go through right there. You have 4 hours you say? Well guess what the security will do... make you wait while people with tighter connections have priority... Not a pleasant place to wait as there's no food/restaurants or seats.
5. Then, they cram you on a "bus" which is just a big van with crappy Aircon and drive you around the tarmac for what seems forever with your carry-on sitting on your lap before you get to the other terminal.
6. You arrive at the other terminal and have to go through another security screening.
7. Then, you think you're done, and make your way upstairs to the transfer desk to get your next boarding pass. Wait wait wait though, what's this? You have to exit a security checkpoint again to get to the transfer desk, meaning on your way back you'll get a 3rd genital handling!!!
   The desk for your airline it will likely be managed by some 3rd party workers and not the airline, so good luck if you have any issues. You get your boarding pass, and then have to turn around and go through the security checkpoint and be screened for a 3rd time!!!
8. Then, you go to the Irish Pub and sit and have a drink and hope that they will not mess up and actually get your bag where it needs to go. In my case, I was shocked when my bag did actually arrive in BOM.

Okay, enough venting... My recommendation for you is the following:
This is also highly recommended as you are connecting to a flight to the USA. They are always paranoid about baggage and you may have trouble interlining the bag to a flight to the USA. I had a headahce and a half interlining a bag from DXB-BOM (Jet) to a BOM-EWR (CO) flight two years back, but that's another story.

Okay, enough venting... suffice to say, just clear immigration and be done with it.

I couldn't agree more. I once made the mistake of transiting through T2 and said never again.

Four hours should be enough for the OP to exit and transfer, although of course this assumes that he is eligible for visa-on-arrival or has a multi-entry visa to the UAE.