He was maybe thinking...

"Maybe" needs to be at the start of these sentences, whereas "perhaps" can be at the start, in the middle or at the end.

He was maybe/perhaps thinking that I had done it on purpose.

No. Put the adverb first, eg
Maybe/perhaps he was thinking that I had done it on purpose.

Or use the appropriate modal:
He may come if you insist.

Thanks, AStars.

...but do native speakers speak like this sometimes? Or is it downright incorrect?

He was maybe thinking...
She was maybe blaming you deep down...

Tom

Mr. Tom...but do native speakers speak like this sometimes?

It would be considered substandard.

For where "perhaps" can go in a sentence, have a look here:

http://dictionary.cambridge.org/grammar/british-grammar/maybe-or-perhaps

http://www.oxforddictionaries

AlpheccaStars Mr. Tom...but do native speakers speak like this sometimes?It would be considered substandard.

I would never write that, but I'd consider it merely informal in conversation. I would not have marked it down If somebody had said it in an oral examination in the days when I was an IELTS examiner

Mr. Tom...but do native speakers speak like this sometimes?

They sometimes do.

Mr. TomOr is it downright incorrect?

I would consider it acceptable in casual speech.

CJ